libsparse: merge adjacent blocks of the same type
When a block is added that is adjacent to another block and of the same
type, merge it. This will be useful for converting regular images to
sparse images, allowing the reader to add a single block at a time and
letting libsparse optimize into larger blocks as it goes.
Does not support merge two blocks that are backed by a data pointer,
only blocks that are backed by a file for now.
Change-Id: I95aa231714cbe01ac194e868c21385806c0bdb97
diff --git a/libsparse/backed_block.c b/libsparse/backed_block.c
index 8c3fab0..629fc28 100644
--- a/libsparse/backed_block.c
+++ b/libsparse/backed_block.c
@@ -21,6 +21,7 @@
#include <string.h>
#include "backed_block.h"
+#include "sparse_defs.h"
struct backed_block {
unsigned int block;
@@ -48,6 +49,7 @@
struct backed_block_list {
struct backed_block *data_blocks;
struct backed_block *last_used;
+ unsigned int block_size;
};
struct backed_block *backed_block_iter_new(struct backed_block_list *bbl)
@@ -109,10 +111,19 @@
return bb->type;
}
-struct backed_block_list *backed_block_list_new(void)
+void backed_block_destroy(struct backed_block *bb)
+{
+ if (bb->type == BACKED_BLOCK_FILE) {
+ free(bb->file.filename);
+ }
+
+ free(bb);
+}
+
+struct backed_block_list *backed_block_list_new(unsigned int block_size)
{
struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1);
-
+ b->block_size = block_size;
return b;
}
@@ -122,11 +133,7 @@
struct backed_block *bb = bbl->data_blocks;
while (bb) {
struct backed_block *next = bb->next;
- if (bb->type == BACKED_BLOCK_FILE) {
- free(bb->file.filename);
- }
-
- free(bb);
+ backed_block_destroy(bb);
bb = next;
}
}
@@ -134,6 +141,63 @@
free(bbl);
}
+/* may free b */
+static int merge_bb(struct backed_block_list *bbl,
+ struct backed_block *a, struct backed_block *b)
+{
+ unsigned int block_len;
+
+ /* Block doesn't exist (possible if one block is the last block) */
+ if (!a || !b) {
+ return -EINVAL;
+ }
+
+ assert(a->block < b->block);
+
+ /* Blocks are of different types */
+ if (a->type != b->type) {
+ return -EINVAL;
+ }
+
+ /* Blocks are not adjacent */
+ block_len = a->len / bbl->block_size; /* rounds down */
+ if (a->block + block_len != b->block) {
+ return -EINVAL;
+ }
+
+ switch (a->type) {
+ case BACKED_BLOCK_DATA:
+ /* Don't support merging data for now */
+ return -EINVAL;
+ case BACKED_BLOCK_FILL:
+ if (a->fill.val != b->fill.val) {
+ return -EINVAL;
+ }
+ break;
+ case BACKED_BLOCK_FILE:
+ if (a->file.filename != b->file.filename ||
+ a->file.offset + a->len != b->file.offset) {
+ return -EINVAL;
+ }
+ break;
+ case BACKED_BLOCK_FD:
+ if (a->fd.fd != b->fd.fd ||
+ a->fd.offset + a->len != b->fd.offset) {
+ return -EINVAL;
+ }
+ break;
+ }
+
+ /* Blocks are compatible and adjacent, with a before b. Merge b into a,
+ * and free b */
+ a->len += b->len;
+ a->next = b->next;
+
+ backed_block_destroy(b);
+
+ return 0;
+}
+
static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb)
{
struct backed_block *bb;
@@ -168,6 +232,9 @@
bb->next = new_bb;
}
+ merge_bb(bbl, new_bb, new_bb->next);
+ merge_bb(bbl, bb, new_bb);
+
return 0;
}
diff --git a/libsparse/backed_block.h b/libsparse/backed_block.h
index ca2ad1d..6926917 100644
--- a/libsparse/backed_block.h
+++ b/libsparse/backed_block.h
@@ -52,7 +52,7 @@
struct backed_block *backed_block_iter_new(struct backed_block_list *bbl);
struct backed_block *backed_block_iter_next(struct backed_block *bb);
-struct backed_block_list *backed_block_list_new(void);
+struct backed_block_list *backed_block_list_new(unsigned int block_size);
void backed_block_list_destroy(struct backed_block_list *bbl);
#endif
diff --git a/libsparse/sparse.c b/libsparse/sparse.c
index 3403604..d778e1d 100644
--- a/libsparse/sparse.c
+++ b/libsparse/sparse.c
@@ -32,7 +32,7 @@
return NULL;
}
- s->backed_block_list = backed_block_list_new();
+ s->backed_block_list = backed_block_list_new(block_size);
if (!s->backed_block_list) {
free(s);
return NULL;