1 | /* |
2 | * QEMU Enhanced Disk Format Cluster functions |
3 | * |
4 | * Copyright IBM, Corp. 2010 |
5 | * |
6 | * Authors: |
7 | * Stefan Hajnoczi <stefanha@linux.vnet.ibm.com> |
8 | * Anthony Liguori <aliguori@us.ibm.com> |
9 | * |
10 | * This work is licensed under the terms of the GNU LGPL, version 2 or later. |
11 | * See the COPYING.LIB file in the top-level directory. |
12 | * |
13 | */ |
14 | |
15 | #include "qemu/osdep.h" |
16 | #include "qed.h" |
17 | |
18 | /** |
19 | * Count the number of contiguous data clusters |
20 | * |
21 | * @s: QED state |
22 | * @table: L2 table |
23 | * @index: First cluster index |
24 | * @n: Maximum number of clusters |
25 | * @offset: Set to first cluster offset |
26 | * |
27 | * This function scans tables for contiguous clusters. A contiguous run of |
28 | * clusters may be allocated, unallocated, or zero. |
29 | */ |
30 | static unsigned int qed_count_contiguous_clusters(BDRVQEDState *s, |
31 | QEDTable *table, |
32 | unsigned int index, |
33 | unsigned int n, |
34 | uint64_t *offset) |
35 | { |
36 | unsigned int end = MIN(index + n, s->table_nelems); |
37 | uint64_t last = table->offsets[index]; |
38 | unsigned int i; |
39 | |
40 | *offset = last; |
41 | |
42 | for (i = index + 1; i < end; i++) { |
43 | if (qed_offset_is_unalloc_cluster(last)) { |
44 | /* Counting unallocated clusters */ |
45 | if (!qed_offset_is_unalloc_cluster(table->offsets[i])) { |
46 | break; |
47 | } |
48 | } else if (qed_offset_is_zero_cluster(last)) { |
49 | /* Counting zero clusters */ |
50 | if (!qed_offset_is_zero_cluster(table->offsets[i])) { |
51 | break; |
52 | } |
53 | } else { |
54 | /* Counting allocated clusters */ |
55 | if (table->offsets[i] != last + s->header.cluster_size) { |
56 | break; |
57 | } |
58 | last = table->offsets[i]; |
59 | } |
60 | } |
61 | return i - index; |
62 | } |
63 | |
64 | /** |
65 | * Find the offset of a data cluster |
66 | * |
67 | * @s: QED state |
68 | * @request: L2 cache entry |
69 | * @pos: Byte position in device |
70 | * @len: Number of bytes (may be shortened on return) |
71 | * @img_offset: Contains offset in the image file on success |
72 | * |
73 | * This function translates a position in the block device to an offset in the |
74 | * image file. The translated offset or unallocated range in the image file is |
75 | * reported back in *img_offset and *len. |
76 | * |
77 | * If the L2 table exists, request->l2_table points to the L2 table cache entry |
78 | * and the caller must free the reference when they are finished. The cache |
79 | * entry is exposed in this way to avoid callers having to read the L2 table |
80 | * again later during request processing. If request->l2_table is non-NULL it |
81 | * will be unreferenced before taking on the new cache entry. |
82 | * |
83 | * On success QED_CLUSTER_FOUND is returned and img_offset/len are a contiguous |
84 | * range in the image file. |
85 | * |
86 | * On failure QED_CLUSTER_L2 or QED_CLUSTER_L1 is returned for missing L2 or L1 |
87 | * table offset, respectively. len is number of contiguous unallocated bytes. |
88 | * |
89 | * Called with table_lock held. |
90 | */ |
91 | int coroutine_fn qed_find_cluster(BDRVQEDState *s, QEDRequest *request, |
92 | uint64_t pos, size_t *len, |
93 | uint64_t *img_offset) |
94 | { |
95 | uint64_t l2_offset; |
96 | uint64_t offset = 0; |
97 | unsigned int index; |
98 | unsigned int n; |
99 | int ret; |
100 | |
101 | /* Limit length to L2 boundary. Requests are broken up at the L2 boundary |
102 | * so that a request acts on one L2 table at a time. |
103 | */ |
104 | *len = MIN(*len, (((pos >> s->l1_shift) + 1) << s->l1_shift) - pos); |
105 | |
106 | l2_offset = s->l1_table->offsets[qed_l1_index(s, pos)]; |
107 | if (qed_offset_is_unalloc_cluster(l2_offset)) { |
108 | *img_offset = 0; |
109 | return QED_CLUSTER_L1; |
110 | } |
111 | if (!qed_check_table_offset(s, l2_offset)) { |
112 | *img_offset = *len = 0; |
113 | return -EINVAL; |
114 | } |
115 | |
116 | ret = qed_read_l2_table(s, request, l2_offset); |
117 | if (ret) { |
118 | goto out; |
119 | } |
120 | |
121 | index = qed_l2_index(s, pos); |
122 | n = qed_bytes_to_clusters(s, qed_offset_into_cluster(s, pos) + *len); |
123 | n = qed_count_contiguous_clusters(s, request->l2_table->table, |
124 | index, n, &offset); |
125 | |
126 | if (qed_offset_is_unalloc_cluster(offset)) { |
127 | ret = QED_CLUSTER_L2; |
128 | } else if (qed_offset_is_zero_cluster(offset)) { |
129 | ret = QED_CLUSTER_ZERO; |
130 | } else if (qed_check_cluster_offset(s, offset)) { |
131 | ret = QED_CLUSTER_FOUND; |
132 | } else { |
133 | ret = -EINVAL; |
134 | } |
135 | |
136 | *len = MIN(*len, |
137 | n * s->header.cluster_size - qed_offset_into_cluster(s, pos)); |
138 | |
139 | out: |
140 | *img_offset = offset; |
141 | return ret; |
142 | } |
143 | |