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

3 files changed, 76 insertions, 9 deletions

diff --git a/libsparse/backed_block.c b/libsparse/backed_block.c
index 8c3fab04a..629fc284f 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 {
 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 @@ enum backed_block_type backed_block_type(struct backed_block *bb)
 	return bb->type;
 }
 
-struct backed_block_list *backed_block_list_new(void)
+void backed_block_destroy(struct backed_block *bb)
 {
-	struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1);
+	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 @@ void backed_block_list_destroy(struct backed_block_list *bbl)
 		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 @@ void backed_block_list_destroy(struct backed_block_list *bbl)
 	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 @@ static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb)
 		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 ca2ad1d9b..692691712 100644
--- a/libsparse/backed_block.h
+++ b/libsparse/backed_block.h
@@ -52,7 +52,7 @@ enum backed_block_type backed_block_type(struct backed_block *bb);
 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 3403604d4..d778e1dc6 100644
--- a/libsparse/sparse.c
+++ b/libsparse/sparse.c
@@ -32,7 +32,7 @@ struct sparse_file *sparse_file_new(unsigned int block_size, int64_t len)
 		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;