4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * * Neither the name of Red Hat nor the names of its contributors may be
16 * used to endorse or promote products derived from this software without
17 * specific prior written permission.
19 * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
22 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
26 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
27 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
28 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
29 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
45 #include "isaligned.h"
52 /* Cap nr_extents to avoid sending over-large replies to the client,
53 * and to avoid a plugin with frequent alternations consuming too much
56 #define MAX_EXTENTS (1 * 1024 * 1024)
58 /* Appendable list of extents. */
59 DEFINE_VECTOR_TYPE (extents
, struct nbdkit_extent
);
61 struct nbdkit_extents
{
64 uint64_t start
, end
; /* end is one byte beyond the end of the range */
66 /* Where we expect the next extent to be added. If
67 * nbdkit_add_extent has never been called this is -1. Note this
68 * field is updated even if we don't actually add the extent because
69 * it's used to check for API violations.
74 NBDKIT_DLL_PUBLIC
struct nbdkit_extents
*
75 nbdkit_extents_new (uint64_t start
, uint64_t end
)
77 struct nbdkit_extents
*r
;
79 if (start
> INT64_MAX
|| end
> INT64_MAX
) {
80 nbdkit_error ("nbdkit_extents_new: "
81 "start (%" PRIu64
") or end (%" PRIu64
") > INT64_MAX",
87 /* 0-length ranges are possible, so start == end is not an error. */
89 nbdkit_error ("nbdkit_extents_new: "
90 "start (%" PRIu64
") >= end (%" PRIu64
")",
96 r
= malloc (sizeof *r
);
98 nbdkit_error ("nbdkit_extents_new: malloc: %m");
101 r
->extents
= (extents
) empty_vector
;
108 NBDKIT_DLL_PUBLIC
void
109 nbdkit_extents_free (struct nbdkit_extents
*exts
)
112 free (exts
->extents
.ptr
);
117 NBDKIT_DLL_PUBLIC
size_t
118 nbdkit_extents_count (const struct nbdkit_extents
*exts
)
120 return exts
->extents
.len
;
123 NBDKIT_DLL_PUBLIC
struct nbdkit_extent
124 nbdkit_get_extent (const struct nbdkit_extents
*exts
, size_t i
)
126 assert (i
< exts
->extents
.len
);
127 return exts
->extents
.ptr
[i
];
130 /* Insert *e in the list at the end. */
132 append_extent (struct nbdkit_extents
*exts
, const struct nbdkit_extent
*e
)
134 if (extents_append (&exts
->extents
, *e
) == -1) {
135 nbdkit_error ("nbdkit_add_extent: realloc: %m");
142 NBDKIT_DLL_PUBLIC
int
143 nbdkit_add_extent (struct nbdkit_extents
*exts
,
144 uint64_t offset
, uint64_t length
, uint32_t type
)
148 /* Extents must be added in strictly ascending, contiguous order. */
149 if (exts
->next
>= 0 && exts
->next
!= offset
) {
150 nbdkit_error ("nbdkit_add_extent: "
151 "extents must be added in ascending order and "
152 "must be contiguous");
156 exts
->next
= offset
+ length
;
158 /* Ignore zero-length extents. */
162 /* Ignore extents beyond the end of the range, or if list is full. */
163 if (offset
>= exts
->end
|| exts
->extents
.len
>= MAX_EXTENTS
)
166 /* Shorten extents that overlap the end of the range. */
167 if (offset
+ length
> exts
->end
) {
168 overlap
= offset
+ length
- exts
->end
;
172 if (exts
->extents
.len
== 0) {
173 /* If there are no existing extents, and the new extent is
174 * entirely before start, ignore it.
176 if (offset
+ length
<= exts
->start
)
179 /* If there are no existing extents, and the new extent is after
180 * start, then this is a bug in the plugin.
182 if (offset
> exts
->start
) {
183 nbdkit_error ("nbdkit_add_extent: "
184 "first extent must not be > start (%" PRIu64
")",
190 /* If there are no existing extents, and the new extent overlaps
191 * start, truncate it so it starts at start.
193 overlap
= exts
->start
- offset
;
198 /* If we get here we are going to either add or extend. */
199 if (exts
->extents
.len
> 0 &&
200 exts
->extents
.ptr
[exts
->extents
.len
-1].type
== type
) {
201 /* Coalesce with the last extent. */
202 exts
->extents
.ptr
[exts
->extents
.len
-1].length
+= length
;
206 /* Add a new extent. */
207 const struct nbdkit_extent e
=
208 { .offset
= offset
, .length
= length
, .type
= type
};
209 return append_extent (exts
, &e
);
213 /* Compute aligned extents on behalf of a filter. */
214 NBDKIT_DLL_PUBLIC
int
215 nbdkit_extents_aligned (struct context
*next_c
,
216 uint32_t count
, uint64_t offset
,
217 uint32_t flags
, uint32_t align
,
218 struct nbdkit_extents
*exts
, int *err
)
220 struct nbdkit_next_ops
*next
= &next_c
->next
;
222 struct nbdkit_extent
*e
, *e2
;
224 assert (IS_ALIGNED (count
| offset
, align
));
226 /* Perform an initial query, then scan for the first unaligned extent. */
227 if (next
->extents (next_c
, count
, offset
, flags
, exts
, err
) == -1)
229 for (i
= 0; i
< exts
->extents
.len
; ++i
) {
230 e
= &exts
->extents
.ptr
[i
];
231 if (!IS_ALIGNED (e
->length
, align
)) {
232 /* If the unalignment is past align, just truncate and return early */
233 if (e
->offset
+ e
->length
> offset
+ align
) {
234 e
->length
= ROUND_DOWN (e
->length
, align
);
235 exts
->extents
.len
= i
+ !!e
->length
;
236 exts
->next
= e
->offset
+ e
->length
;
240 /* Otherwise, coalesce until we have at least align bytes, which
241 * may require further queries. The type bits are:
242 * NBDKIT_EXTENT_HOLE (1<<0)
243 * NBDKIT_EXTENT_ZERO (1<<1)
244 * and the NBD protocol says any future bits will also have the
245 * desired property that returning '0' is the safe default for
246 * the generic case. Thus, performing the bitwise-and
247 * intersection of the types of underlying extents gives the
248 * correct type for our merged extent.
251 while (e
->length
< align
) {
252 if (exts
->extents
.len
> 1) {
253 e
->length
+= exts
->extents
.ptr
[1].length
;
254 e
->type
&= exts
->extents
.ptr
[1].type
;
255 extents_remove (&exts
->extents
, 1);
258 /* The plugin needs a fresh extents object each time, but
259 * with care, we can merge it into the callers' exts.
262 CLEANUP_EXTENTS_FREE
struct nbdkit_extents
*extents2
= NULL
;
264 extents2
= nbdkit_extents_new (e
->offset
+ e
->length
,
266 if (extents2
== NULL
) {
270 if (next
->extents (next_c
, align
- e
->length
,
272 flags
& ~NBDKIT_FLAG_REQ_ONE
,
273 extents2
, err
) == -1)
275 e2
= &extents2
->extents
.ptr
[0];
276 assert (e2
->offset
== e
->offset
+ e
->length
);
277 e2
->offset
= e
->offset
;
278 e2
->length
+= e
->length
;
282 exts
->extents
= extents2
->extents
;
283 extents2
->extents
= tmp
;
287 exts
->extents
.len
= 1;
288 exts
->next
= e
->offset
+ e
->length
;
292 /* Once we get here, all extents are aligned. */
296 /* This is a convenient wrapper around next_ops->extents which can be
297 * used from filters where you want to get a complete set of extents
298 * covering the region [offset..offset+count-1].
300 NBDKIT_DLL_PUBLIC
struct nbdkit_extents
*
301 nbdkit_extents_full (struct context
*next_c
,
302 uint32_t count
, uint64_t offset
, uint32_t flags
,
305 struct nbdkit_next_ops
*next
= &next_c
->next
;
306 struct nbdkit_extents
*ret
;
308 /* Clear REQ_ONE to ask the plugin for as much information as it is
309 * willing to return (the plugin may still truncate if it is too
310 * costly to provide everything).
312 flags
&= ~NBDKIT_FLAG_REQ_ONE
;
314 ret
= nbdkit_extents_new (offset
, offset
+count
);
315 if (ret
== NULL
) goto error0
;
318 const uint64_t old_offset
= offset
;
321 CLEANUP_EXTENTS_FREE
struct nbdkit_extents
*t
322 = nbdkit_extents_new (offset
, offset
+count
);
323 if (t
== NULL
) goto error1
;
325 if (next
->extents (next_c
, count
, offset
, flags
, t
, err
) == -1)
328 for (i
= 0; i
< nbdkit_extents_count (t
); ++i
) {
329 const struct nbdkit_extent e
= nbdkit_get_extent (t
, i
);
330 if (nbdkit_add_extent (ret
, e
.offset
, e
.length
, e
.type
) == -1)
333 assert (e
.length
<= count
);
338 /* If the plugin is behaving we must make forward progress. */
339 assert (offset
> old_offset
);
347 nbdkit_extents_free (ret
);