/* 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>
*/
#include <linux/kernel.h>
#include <linux/string.h>
#include "loop_file_fmt.h"
#include "loop_file_fmt_qcow_main.h"
#include "loop_file_fmt_qcow_cache.h"
#include "loop_file_fmt_qcow_cluster.h"
/*
* 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 = sizeof(u64) * (
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);
}
/*
* Checks how many clusters in a given L2 slice are contiguous in the image
* file. As soon as one of the flags in the bitmask stop_flags changes compared
* to the first cluster, the search is stopped and the cluster is not counted
* as contiguous. (This allows it, for example, to stop at the first compressed
* cluster which may require a different handling)
*/
static int __xloop_file_fmt_qcow_cluster_count_contiguous(
struct xloop_file_fmt *xlo_fmt, int nb_clusters, int cluster_size,
u64 *l2_slice, u64 stop_flags)
{
int i;
enum xloop_file_fmt_qcow_cluster_type first_cluster_type;
u64 mask = stop_flags | L2E_OFFSET_MASK | QCOW_OFLAG_COMPRESSED;
u64 first_entry = be64_to_cpu(l2_slice[0]);
u64 offset = first_entry & mask;
first_cluster_type = xloop_file_fmt_qcow_get_cluster_type(xlo_fmt,
first_entry);
if (first_cluster_type == QCOW_CLUSTER_UNALLOCATED) {
return 0;
}
/* must be allocated */
ASSERT(first_cluster_type == QCOW_CLUSTER_NORMAL ||
first_cluster_type == QCOW_CLUSTER_ZERO_ALLOC);
for (i = 0; i < nb_clusters; i++) {
u64 l2_entry = be64_to_cpu(l2_slice[i]) & mask;
if (offset + (u64) i * cluster_size != l2_entry) {
break;
}
}
return i;
}
/*
* Checks how many consecutive unallocated clusters in a given L2
* slice have the same cluster type.
*/
static int __xloop_file_fmt_qcow_cluster_count_contiguous_unallocated(
struct xloop_file_fmt *xlo_fmt, int nb_clusters, u64 *l2_slice,
enum xloop_file_fmt_qcow_cluster_type wanted_type)
{
int i;
ASSERT(wanted_type == QCOW_CLUSTER_ZERO_PLAIN ||
wanted_type == QCOW_CLUSTER_UNALLOCATED);
for (i = 0; i < nb_clusters; i++) {
u64 entry = be64_to_cpu(l2_slice[i]);
enum xloop_file_fmt_qcow_cluster_type type =
xloop_file_fmt_qcow_get_cluster_type(xlo_fmt, entry);
if (type != wanted_type) {
break;
}
}
return i;
}
/*
* For a given offset of the virtual disk, find the cluster type and offset in
* the qcow2 file. The offset is stored in *cluster_offset.
*
* 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
* cluster type and (if applicable) are stored contiguously in the image file.
* Compressed clusters are always returned one by one.
*
* Returns the cluster type (QCOW2_CLUSTER_*) on success, -errno in error
* cases.
*/
int xloop_file_fmt_qcow_cluster_get_offset(struct xloop_file_fmt *xlo_fmt,
u64 offset, unsigned int *bytes, u64 *cluster_offset)
{
struct xloop_file_fmt_qcow_data *qcow_data = xlo_fmt->private_data;
unsigned int l2_index;
u64 l1_index, l2_offset, *l2_slice;
int c;
unsigned int offset_in_cluster;
u64 bytes_available, bytes_needed, nb_clusters;
enum xloop_file_fmt_qcow_cluster_type type;
int ret;
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;
}
*cluster_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_CLUSTER_UNALLOCATED;
goto out;
}
l2_offset = qcow_data->l1_table[l1_index] & L1E_OFFSET_MASK;
if (!l2_offset) {
type = QCOW_CLUSTER_UNALLOCATED;
goto out;
}
if (xloop_file_fmt_qcow_offset_into_cluster(qcow_data, l2_offset)) {
printk_ratelimited(KERN_ERR "xloop_file_fmt_qcow: 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);
*cluster_offset = be64_to_cpu(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_cluster_type(xlo_fmt, *cluster_offset);
if (qcow_data->qcow_version < 3 && (
type == QCOW_CLUSTER_ZERO_PLAIN ||
type == QCOW_CLUSTER_ZERO_ALLOC)) {
printk_ratelimited(KERN_ERR "xloop_file_fmt_qcow: 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_CLUSTER_COMPRESSED:
if (xloop_file_fmt_qcow_has_data_file(xlo_fmt)) {
printk_ratelimited(KERN_ERR "xloop_file_fmt_qcow: "
"compressed cluster entry found in image with "
"external data file (L2 offset: %llx, "
"L2 index: %x)", l2_offset, l2_index);
ret = -EIO;
goto fail;
}
/* Compressed clusters can only be processed one by one */
c = 1;
*cluster_offset &= L2E_COMPRESSED_OFFSET_SIZE_MASK;
break;
case QCOW_CLUSTER_ZERO_PLAIN:
case QCOW_CLUSTER_UNALLOCATED:
/* how many empty clusters ? */
c = __xloop_file_fmt_qcow_cluster_count_contiguous_unallocated(
xlo_fmt, nb_clusters, &l2_slice[l2_index], type);
*cluster_offset = 0;
break;
case QCOW_CLUSTER_ZERO_ALLOC:
case QCOW_CLUSTER_NORMAL:
/* how many allocated clusters ? */
c = __xloop_file_fmt_qcow_cluster_count_contiguous(xlo_fmt,
nb_clusters, qcow_data->cluster_size,
&l2_slice[l2_index], QCOW_OFLAG_ZERO);
*cluster_offset &= L2E_OFFSET_MASK;
if (xloop_file_fmt_qcow_offset_into_cluster(qcow_data,
*cluster_offset)) {
printk_ratelimited(KERN_ERR "xloop_file_fmt_qcow: "
"cluster allocation offset %llx unaligned "
"(L2 offset: %llx, L2 index: %x)\n",
*cluster_offset, l2_offset, l2_index);
ret = -EIO;
goto fail;
}
if (xloop_file_fmt_qcow_has_data_file(xlo_fmt) &&
*cluster_offset != offset - offset_in_cluster) {
printk_ratelimited(KERN_ERR "xloop_file_fmt_qcow: "
"external data file host cluster offset %llx "
"does not match guest cluster offset: %llx, "
"L2 index: %x)", *cluster_offset,
offset - offset_in_cluster, l2_index);
ret = -EIO;
goto fail;
}
break;
default:
BUG();
}
xloop_file_fmt_qcow_cache_put(xlo_fmt, (void **) &l2_slice);
bytes_available = (s64) c * qcow_data->cluster_size;
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;
return type;
fail:
xloop_file_fmt_qcow_cache_put(xlo_fmt, (void **) &l2_slice);
return ret;
}