1298800caSStefan Hajnoczi /*
2298800caSStefan Hajnoczi * QEMU Enhanced Disk Format Cluster functions
3298800caSStefan Hajnoczi *
4298800caSStefan Hajnoczi * Copyright IBM, Corp. 2010
5298800caSStefan Hajnoczi *
6298800caSStefan Hajnoczi * Authors:
7298800caSStefan Hajnoczi * Stefan Hajnoczi <stefanha@linux.vnet.ibm.com>
8298800caSStefan Hajnoczi * Anthony Liguori <aliguori@us.ibm.com>
9298800caSStefan Hajnoczi *
10298800caSStefan Hajnoczi * This work is licensed under the terms of the GNU LGPL, version 2 or later.
11298800caSStefan Hajnoczi * See the COPYING.LIB file in the top-level directory.
12298800caSStefan Hajnoczi *
13298800caSStefan Hajnoczi */
14298800caSStefan Hajnoczi
1580c71a24SPeter Maydell #include "qemu/osdep.h"
16298800caSStefan Hajnoczi #include "qed.h"
17298800caSStefan Hajnoczi
18298800caSStefan Hajnoczi /**
19298800caSStefan Hajnoczi * Count the number of contiguous data clusters
20298800caSStefan Hajnoczi *
21298800caSStefan Hajnoczi * @s: QED state
22298800caSStefan Hajnoczi * @table: L2 table
23298800caSStefan Hajnoczi * @index: First cluster index
24298800caSStefan Hajnoczi * @n: Maximum number of clusters
25298800caSStefan Hajnoczi * @offset: Set to first cluster offset
26298800caSStefan Hajnoczi *
2721df65b6SAnthony Liguori * This function scans tables for contiguous clusters. A contiguous run of
2821df65b6SAnthony Liguori * clusters may be allocated, unallocated, or zero.
29298800caSStefan Hajnoczi */
qed_count_contiguous_clusters(BDRVQEDState * s,QEDTable * table,unsigned int index,unsigned int n,uint64_t * offset)30298800caSStefan Hajnoczi static unsigned int qed_count_contiguous_clusters(BDRVQEDState *s,
31298800caSStefan Hajnoczi QEDTable *table,
32298800caSStefan Hajnoczi unsigned int index,
33298800caSStefan Hajnoczi unsigned int n,
34298800caSStefan Hajnoczi uint64_t *offset)
35298800caSStefan Hajnoczi {
36298800caSStefan Hajnoczi unsigned int end = MIN(index + n, s->table_nelems);
37298800caSStefan Hajnoczi uint64_t last = table->offsets[index];
38298800caSStefan Hajnoczi unsigned int i;
39298800caSStefan Hajnoczi
40298800caSStefan Hajnoczi *offset = last;
41298800caSStefan Hajnoczi
42298800caSStefan Hajnoczi for (i = index + 1; i < end; i++) {
4321df65b6SAnthony Liguori if (qed_offset_is_unalloc_cluster(last)) {
4421df65b6SAnthony Liguori /* Counting unallocated clusters */
4521df65b6SAnthony Liguori if (!qed_offset_is_unalloc_cluster(table->offsets[i])) {
4621df65b6SAnthony Liguori break;
4721df65b6SAnthony Liguori }
4821df65b6SAnthony Liguori } else if (qed_offset_is_zero_cluster(last)) {
4921df65b6SAnthony Liguori /* Counting zero clusters */
5021df65b6SAnthony Liguori if (!qed_offset_is_zero_cluster(table->offsets[i])) {
51298800caSStefan Hajnoczi break;
52298800caSStefan Hajnoczi }
53298800caSStefan Hajnoczi } else {
54298800caSStefan Hajnoczi /* Counting allocated clusters */
55298800caSStefan Hajnoczi if (table->offsets[i] != last + s->header.cluster_size) {
56298800caSStefan Hajnoczi break;
57298800caSStefan Hajnoczi }
58298800caSStefan Hajnoczi last = table->offsets[i];
59298800caSStefan Hajnoczi }
60298800caSStefan Hajnoczi }
61298800caSStefan Hajnoczi return i - index;
62298800caSStefan Hajnoczi }
63298800caSStefan Hajnoczi
64298800caSStefan Hajnoczi /**
65298800caSStefan Hajnoczi * Find the offset of a data cluster
66298800caSStefan Hajnoczi *
67298800caSStefan Hajnoczi * @s: QED state
68298800caSStefan Hajnoczi * @request: L2 cache entry
69298800caSStefan Hajnoczi * @pos: Byte position in device
700f21b7a1SKevin Wolf * @len: Number of bytes (may be shortened on return)
710f21b7a1SKevin Wolf * @img_offset: Contains offset in the image file on success
72298800caSStefan Hajnoczi *
73298800caSStefan Hajnoczi * This function translates a position in the block device to an offset in the
740f21b7a1SKevin Wolf * image file. The translated offset or unallocated range in the image file is
750f21b7a1SKevin Wolf * reported back in *img_offset and *len.
76298800caSStefan Hajnoczi *
77298800caSStefan Hajnoczi * If the L2 table exists, request->l2_table points to the L2 table cache entry
78298800caSStefan Hajnoczi * and the caller must free the reference when they are finished. The cache
79298800caSStefan Hajnoczi * entry is exposed in this way to avoid callers having to read the L2 table
80298800caSStefan Hajnoczi * again later during request processing. If request->l2_table is non-NULL it
81298800caSStefan Hajnoczi * will be unreferenced before taking on the new cache entry.
820f21b7a1SKevin Wolf *
830f21b7a1SKevin Wolf * On success QED_CLUSTER_FOUND is returned and img_offset/len are a contiguous
840f21b7a1SKevin Wolf * range in the image file.
850f21b7a1SKevin Wolf *
860f21b7a1SKevin Wolf * On failure QED_CLUSTER_L2 or QED_CLUSTER_L1 is returned for missing L2 or L1
870f21b7a1SKevin Wolf * table offset, respectively. len is number of contiguous unallocated bytes.
88*1f01e50bSPaolo Bonzini *
89*1f01e50bSPaolo Bonzini * Called with table_lock held.
90298800caSStefan Hajnoczi */
qed_find_cluster(BDRVQEDState * s,QEDRequest * request,uint64_t pos,size_t * len,uint64_t * img_offset)9187f0d882SKevin Wolf int coroutine_fn qed_find_cluster(BDRVQEDState *s, QEDRequest *request,
9287f0d882SKevin Wolf uint64_t pos, size_t *len,
9387f0d882SKevin Wolf uint64_t *img_offset)
94298800caSStefan Hajnoczi {
95298800caSStefan Hajnoczi uint64_t l2_offset;
96a8165d2dSKevin Wolf uint64_t offset = 0;
97a8165d2dSKevin Wolf unsigned int index;
98a8165d2dSKevin Wolf unsigned int n;
99a8165d2dSKevin Wolf int ret;
100298800caSStefan Hajnoczi
101298800caSStefan Hajnoczi /* Limit length to L2 boundary. Requests are broken up at the L2 boundary
102298800caSStefan Hajnoczi * so that a request acts on one L2 table at a time.
103298800caSStefan Hajnoczi */
1040f21b7a1SKevin Wolf *len = MIN(*len, (((pos >> s->l1_shift) + 1) << s->l1_shift) - pos);
105298800caSStefan Hajnoczi
106298800caSStefan Hajnoczi l2_offset = s->l1_table->offsets[qed_l1_index(s, pos)];
10721df65b6SAnthony Liguori if (qed_offset_is_unalloc_cluster(l2_offset)) {
1080f21b7a1SKevin Wolf *img_offset = 0;
1090f21b7a1SKevin Wolf return QED_CLUSTER_L1;
110298800caSStefan Hajnoczi }
111298800caSStefan Hajnoczi if (!qed_check_table_offset(s, l2_offset)) {
1120f21b7a1SKevin Wolf *img_offset = *len = 0;
1130f21b7a1SKevin Wolf return -EINVAL;
114298800caSStefan Hajnoczi }
115298800caSStefan Hajnoczi
116a8165d2dSKevin Wolf ret = qed_read_l2_table(s, request, l2_offset);
117a8165d2dSKevin Wolf if (ret) {
118a8165d2dSKevin Wolf goto out;
119a8165d2dSKevin Wolf }
120298800caSStefan Hajnoczi
121a8165d2dSKevin Wolf index = qed_l2_index(s, pos);
1220f21b7a1SKevin Wolf n = qed_bytes_to_clusters(s, qed_offset_into_cluster(s, pos) + *len);
123a8165d2dSKevin Wolf n = qed_count_contiguous_clusters(s, request->l2_table->table,
124a8165d2dSKevin Wolf index, n, &offset);
125a8165d2dSKevin Wolf
126a8165d2dSKevin Wolf if (qed_offset_is_unalloc_cluster(offset)) {
127a8165d2dSKevin Wolf ret = QED_CLUSTER_L2;
128a8165d2dSKevin Wolf } else if (qed_offset_is_zero_cluster(offset)) {
129a8165d2dSKevin Wolf ret = QED_CLUSTER_ZERO;
130a8165d2dSKevin Wolf } else if (qed_check_cluster_offset(s, offset)) {
131a8165d2dSKevin Wolf ret = QED_CLUSTER_FOUND;
132a8165d2dSKevin Wolf } else {
133a8165d2dSKevin Wolf ret = -EINVAL;
134a8165d2dSKevin Wolf }
135a8165d2dSKevin Wolf
1360f21b7a1SKevin Wolf *len = MIN(*len,
137a8165d2dSKevin Wolf n * s->header.cluster_size - qed_offset_into_cluster(s, pos));
138a8165d2dSKevin Wolf
139a8165d2dSKevin Wolf out:
1400f21b7a1SKevin Wolf *img_offset = offset;
1410f21b7a1SKevin Wolf return ret;
142298800caSStefan Hajnoczi }
143