AOSP: e2fsdroid: Fix logical block sequencing in BaseFS.

By iterating over blocks to write BaseFS, holes in the extent tree are
skipped. This is problematic because the purpose of BaseFS is to
preserve the logical to physical block assignment between builds. By not
preserving the location of holes, the assignment can be incorrect.

For example, consider the following block list for a file:
   1 2 3 0 4 5

If this is recorded as:
   1 2 3 4 5

If the first block changes to a hole, the intended mapping will not be
preserved at all:
   0 1 2 0 3

This patch makes two changes to e2fsdroid to fix this. The first change
is that holes are now recorded in BaseFS, by iterating over the extent
tree rather than the block list, and inserting zeroes where appropriate.

The second change is that the block allocator now recognizes when blocks
have been skipped (either to deduplication or to holes), and skips the
same number of logical blocks in BaseFS as well.

In a Virtual A/B simulation, this reduces the COW snapshot size by
approximately 100MB.

Bug: 139201772
Test: m target-files-package, inspect .map files
From AOSP commit: d391f3bf38cbe51718d5c3c0bb3e72b1a9978625

2 files changed, 99 insertions, 5 deletions

diff --git a/contrib/android/basefs_allocator.c b/contrib/android/basefs_allocator.c
index 325aed852..2c5b92b42 100644
--- a/contrib/android/basefs_allocator.c
+++ b/contrib/android/basefs_allocator.c
@@ -9,6 +9,8 @@
 struct base_fs_allocator {
 	struct ext2fs_hashmap *entries;
 	struct basefs_entry *cur_entry;
+	/* The next expected logical block to allocate for cur_entry. */
+	blk64_t next_lblk;
 	/* Blocks which are definitely owned by a single inode in BaseFS. */
 	ext2fs_block_bitmap exclusive_block_map;
 	/* Blocks which are available to the first inode that requests it. */
@@ -239,6 +241,42 @@ static int get_next_block(ext2_filsys fs, struct base_fs_allocator *allocator,
 	return -1;
 }
 
+/*
+ * BaseFS lists blocks in logical block order. However, the allocator hook is
+ * only called if a block needs to be allocated. In the case of a deduplicated
+ * block, or a hole, the hook is not invoked. This means the next block
+ * allocation request will be out of sequence. For example, consider if BaseFS
+ * specifies the following (0 being a hole):
+ *     1 2 3 0 4 5
+ *
+ * If the new file has a hole at logical block 0, we could accidentally
+ * shift the entire expected block list as follows:
+ *     0 1 2 0 3 4
+ *
+ * To account for this, we track the next expected logical block in the
+ * allocator. If the current request is for a later logical block, we skip and
+ * free the intermediate physical blocks that would have been allocated. This
+ * ensures the original block assignment is respected.
+ */
+static void skip_blocks(ext2_filsys fs, struct base_fs_allocator *allocator,
+			struct blk_alloc_ctx *ctx)
+{
+	blk64_t block;
+	struct block_range_list *list = &allocator->cur_entry->blocks;
+	ext2fs_block_bitmap exclusive_map = allocator->exclusive_block_map;
+
+	while (list->head && allocator->next_lblk < ctx->lblk) {
+		block = consume_next_block(list);
+		if (block >= ext2fs_blocks_count(fs->super))
+			continue;
+		if (ext2fs_test_block_bitmap2(exclusive_map, block)) {
+			ext2fs_unmark_block_bitmap2(exclusive_map, block);
+			ext2fs_unmark_block_bitmap2(fs->block_map, block);
+		}
+		allocator->next_lblk++;
+	}
+}
+
 static errcode_t basefs_block_allocator(ext2_filsys fs, blk64_t goal,
 					blk64_t *ret, struct blk_alloc_ctx *ctx)
 {
@@ -248,6 +286,10 @@ static errcode_t basefs_block_allocator(ext2_filsys fs, blk64_t goal,
 	ext2fs_block_bitmap dedup_map = allocator->dedup_block_map;
 
 	if (e && ctx && (ctx->flags & BLOCK_ALLOC_DATA)) {
+		if (allocator->next_lblk < ctx->lblk)
+			skip_blocks(fs, allocator, ctx);
+		allocator->next_lblk = ctx->lblk + 1;
+
 		if (!get_next_block(fs, allocator, &e->blocks, ret))
 			return 0;
 	}
@@ -287,10 +329,12 @@ errcode_t base_fs_alloc_set_target(ext2_filsys fs, const char *target_path,
 	if (mode != S_IFREG)
 		return 0;
 
-	if (allocator)
+	if (allocator) {
 		allocator->cur_entry = ext2fs_hashmap_lookup(allocator->entries,
 						      target_path,
 						      strlen(target_path));
+		allocator->next_lblk = 0;
+	}
 	return 0;
 }
 
diff --git a/contrib/android/fsmap.c b/contrib/android/fsmap.c
index 36adb7f0a..9ee8472dc 100644
--- a/contrib/android/fsmap.c
+++ b/contrib/android/fsmap.c
@@ -23,11 +23,51 @@ static int walk_block(ext2_filsys fs  EXT2FS_ATTR((unused)), blk64_t *blocknr,
 	return format->add_block(fs, *blocknr, blockcnt < 0, format->private);
 }
 
+static errcode_t ino_iter_extents(ext2_filsys fs, ext2_ino_t ino,
+				  ext2_extent_handle_t extents,
+				  struct walk_ext_priv_data *pdata)
+{
+	blk64_t block;
+	errcode_t retval;
+	blk64_t next_lblk = 0;
+	int op = EXT2_EXTENT_ROOT;
+	struct ext2fs_extent extent;
+	struct fsmap_format *format = pdata->format;
+
+	for (;;) {
+		retval = ext2fs_extent_get(extents, op, &extent);
+		if (retval)
+			break;
+
+		op = EXT2_EXTENT_NEXT;
+
+		if ((extent.e_flags & EXT2_EXTENT_FLAGS_SECOND_VISIT) ||
+		    !(extent.e_flags & EXT2_EXTENT_FLAGS_LEAF))
+			continue;
+
+		for (; next_lblk < extent.e_lblk; next_lblk++)
+			format->add_block(fs, 0, 0, format->private);
+
+		block = extent.e_pblk;
+		for (; next_lblk < extent.e_lblk + extent.e_len; next_lblk++)
+			format->add_block(fs, block++, 0, format->private);
+	}
+
+	if (retval == EXT2_ET_EXTENT_NO_NEXT)
+		retval = 0;
+	if (retval) {
+		com_err(__func__, retval, ("getting extents of ino \"%u\""),
+			ino);
+	}
+	return retval;
+}
+
 static errcode_t ino_iter_blocks(ext2_filsys fs, ext2_ino_t ino,
 				 struct walk_ext_priv_data *pdata)
 {
 	errcode_t retval;
 	struct ext2_inode inode;
+	ext2_extent_handle_t extents;
 	struct fsmap_format *format = pdata->format;
 
 	retval = ext2fs_read_inode(fs, ino, &inode);
@@ -38,10 +78,20 @@ static errcode_t ino_iter_blocks(ext2_filsys fs, ext2_ino_t ino,
 		return format->inline_data(&(inode.i_block[0]),
 					   format->private);
 
-	retval = ext2fs_block_iterate3(fs, ino, 0, NULL, walk_block, pdata);
-	if (retval)
-		com_err(__func__, retval, _("listing blocks of ino \"%u\""),
-			ino);
+	retval = ext2fs_extent_open(fs, ino, &extents);
+	if (retval == EXT2_ET_INODE_NOT_EXTENT) {
+		retval = ext2fs_block_iterate3(fs, ino, BLOCK_FLAG_READ_ONLY,
+			NULL, walk_block, pdata);
+		if (retval) {
+			com_err(__func__, retval, _("listing blocks of ino \"%u\""),
+				ino);
+		}
+		return retval;
+	}
+
+	retval = ino_iter_extents(fs, ino, extents, pdata);
+
+	ext2fs_extent_free(extents);
 	return retval;
 }