add option to make_ext4fs to record blocks for each file

Add the -B option to make_ext4fs, which causes it to record the block
ranges used for each (regular) file in the image.  We can use this
information to construct more efficient block-based incremental OTAs.

Bug: 16984795
Change-Id: I2a5325bb89948f63c76e93fdfa84c51f9b050104

10 files changed, 100 insertions, 33 deletions

diff --git a/ext4_utils/allocate.c b/ext4_utils/allocate.c
index 6397270f..cca3dc13 100644
--- a/ext4_utils/allocate.c
+++ b/ext4_utils/allocate.c
@@ -22,18 +22,6 @@
 #include <stdio.h>
 #include <stdlib.h>
 
-struct region_list {
-	struct region *first;
-	struct region *last;
-	struct region *iter;
-	u32 partial_iter;
-};
-
-struct block_allocation {
-	struct region_list list;
-	struct region_list oob_list;
-};
-
 struct region {
 	u32 block;
 	u32 len;
@@ -76,6 +64,8 @@ struct block_allocation *create_allocation()
 	alloc->list.partial_iter = 0;
 	alloc->oob_list.iter = NULL;
 	alloc->oob_list.partial_iter = 0;
+	alloc->filename = NULL;
+	alloc->next = NULL;
 	return alloc;
 }
 
@@ -137,9 +127,7 @@ static void dump_starting_from(struct region *reg)
 {
 	for (; reg; reg = reg->next) {
 		printf("%p: Blocks %d-%d (%d)\n", reg,
-				reg->bg * info.blocks_per_group + reg->block,
-				reg->bg * info.blocks_per_group + reg->block + reg->len - 1,
-				reg->len);
+			   reg->block, reg->block + reg->len - 1, reg->len)
 	}
 }
 
@@ -153,6 +141,19 @@ static void dump_region_lists(struct block_allocation *alloc) {
 }
 #endif
 
+void print_blocks(FILE* f, struct block_allocation *alloc)
+{
+	struct region *reg;
+	for (reg = alloc->list.first; reg; reg = reg->next) {
+		if (reg->len == 1) {
+			fprintf(f, " %d", reg->block);
+		} else {
+			fprintf(f, " %d-%d", reg->block, reg->block + reg->len - 1);
+		}
+	}
+	fputc('\n', f);
+}
+
 void append_region(struct block_allocation *alloc,
 		u32 block, u32 len, int bg_num)
 {
diff --git a/ext4_utils/allocate.h b/ext4_utils/allocate.h
index a0999e4a..5c26792c 100644
--- a/ext4_utils/allocate.h
+++ b/ext4_utils/allocate.h
@@ -21,7 +21,22 @@
 
 #include "ext4_utils.h"
 
-struct block_allocation;
+struct region;
+
+struct region_list {
+	struct region *first;
+	struct region *last;
+	struct region *iter;
+	u32 partial_iter;
+};
+
+struct block_allocation {
+	struct region_list list;
+	struct region_list oob_list;
+	char* filename;
+	struct block_allocation* next;
+};
+
 
 void block_allocator_init();
 void block_allocator_free();
@@ -54,5 +69,6 @@ void append_region(struct block_allocation *alloc,
 	u32 block, u32 len, int bg);
 struct block_allocation *create_allocation();
 int append_oob_allocation(struct block_allocation *alloc, u32 len);
+void print_blocks(FILE* f, struct block_allocation *alloc);
 
 #endif
diff --git a/ext4_utils/contents.c b/ext4_utils/contents.c
index 4aa287f2..fb3a38dc 100644
--- a/ext4_utils/contents.c
+++ b/ext4_utils/contents.c
@@ -38,6 +38,12 @@
 #define S_IFLNK 0  /* used by make_link, not needed under mingw */
 #endif
 
+static struct block_allocation* saved_allocation_head = NULL;
+
+struct block_allocation* get_saved_allocation_chain() {
+	return saved_allocation_head;
+}
+
 static u32 dentry_size(u32 entries, struct dentry *dentries)
 {
 	u32 len = 24;
@@ -186,8 +192,13 @@ u32 make_file(const char *filename, u64 len)
 		return EXT4_ALLOCATE_FAILED;
 	}
 
-	if (len > 0)
-		inode_allocate_file_extents(inode, len, filename);
+	if (len > 0) {
+		struct block_allocation* alloc = inode_allocate_file_extents(inode, len, filename);
+
+		alloc->filename = strdup(filename);
+		alloc->next = saved_allocation_head;
+		saved_allocation_head = alloc;
+	}
 
 	inode->i_mode = S_IFREG;
 	inode->i_links_count = 1;
@@ -476,4 +487,3 @@ int inode_set_capabilities(u32 inode_num, uint64_t capabilities) {
 	return xattr_add(inode_num, EXT4_XATTR_INDEX_SECURITY,
 		XATTR_CAPS_SUFFIX, &cap_data, sizeof(cap_data));
 }
-
diff --git a/ext4_utils/contents.h b/ext4_utils/contents.h
index 42720000..e57687e0 100644
--- a/ext4_utils/contents.h
+++ b/ext4_utils/contents.h
@@ -40,4 +40,6 @@ u32 make_link(const char *link);
 int inode_set_permissions(u32 inode_num, u16 mode, u16 uid, u16 gid, u32 mtime);
 int inode_set_selinux(u32 inode_num, const char *secon);
 int inode_set_capabilities(u32 inode_num, uint64_t capabilities);
+struct block_allocation* get_saved_allocation_chain();
+
 #endif
diff --git a/ext4_utils/ext4_utils.h b/ext4_utils/ext4_utils.h
index 190fdb3f..499753fd 100644
--- a/ext4_utils/ext4_utils.h
+++ b/ext4_utils/ext4_utils.h
@@ -158,7 +158,8 @@ struct selabel_handle;
 int make_ext4fs_internal(int fd, const char *directory,
 						 const char *mountpoint, fs_config_func_t fs_config_func, int gzip,
 						 int sparse, int crc, int wipe,
-						 struct selabel_handle *sehnd, int verbose, time_t fixed_time);
+						 struct selabel_handle *sehnd, int verbose, time_t fixed_time,
+						 FILE* block_list_file);
 
 int read_ext(int fd, int verbose);
 
diff --git a/ext4_utils/extent.c b/ext4_utils/extent.c
index abb30ce4..7142c8bb 100644
--- a/ext4_utils/extent.c
+++ b/ext4_utils/extent.c
@@ -202,7 +202,7 @@ u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len,
 
 /* Allocates enough blocks to hold len bytes, queues them to be written
    from a file, and connects them to an inode. */
-void inode_allocate_file_extents(struct ext4_inode *inode, u64 len,
+struct block_allocation* inode_allocate_file_extents(struct ext4_inode *inode, u64 len,
 	const char *filename)
 {
 	struct block_allocation *alloc;
@@ -214,8 +214,7 @@ void inode_allocate_file_extents(struct ext4_inode *inode, u64 len,
 	}
 
 	extent_create_backing_file(alloc, len, filename);
-
-	free_alloc(alloc);
+    return alloc;
 }
 
 /* Allocates enough blocks to hold len bytes and connects them to an inode */
diff --git a/ext4_utils/extent.h b/ext4_utils/extent.h
index a1ddeb15..a78a7b0a 100644
--- a/ext4_utils/extent.h
+++ b/ext4_utils/extent.h
@@ -21,8 +21,8 @@
 #include "ext4_utils.h"
 
 void inode_allocate_extents(struct ext4_inode *inode, u64 len);
-void inode_allocate_file_extents(struct ext4_inode *inode, u64 len,
-	const char *filename);
+struct block_allocation* inode_allocate_file_extents(
+	struct ext4_inode *inode, u64 len, const char *filename);
 u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len,
 	u64 backing_len);
 void free_extent_blocks();
diff --git a/ext4_utils/make_ext4fs.c b/ext4_utils/make_ext4fs.c
index a4904153..2f89ae8a 100644
--- a/ext4_utils/make_ext4fs.c
+++ b/ext4_utils/make_ext4fs.c
@@ -396,7 +396,7 @@ int make_ext4fs_sparse_fd(int fd, long long len,
 	reset_ext4fs_info();
 	info.len = len;
 
-	return make_ext4fs_internal(fd, NULL, mountpoint, NULL, 0, 1, 0, 0, sehnd, 0, -1);
+	return make_ext4fs_internal(fd, NULL, mountpoint, NULL, 0, 1, 0, 0, sehnd, 0, -1, NULL);
 }
 
 int make_ext4fs(const char *filename, long long len,
@@ -414,7 +414,7 @@ int make_ext4fs(const char *filename, long long len,
 		return EXIT_FAILURE;
 	}
 
-	status = make_ext4fs_internal(fd, NULL, mountpoint, NULL, 0, 0, 0, 1, sehnd, 0, -1);
+	status = make_ext4fs_internal(fd, NULL, mountpoint, NULL, 0, 0, 0, 1, sehnd, 0, -1, NULL);
 	close(fd);
 
 	return status;
@@ -483,7 +483,8 @@ static char *canonicalize_rel_slashes(const char *str)
 int make_ext4fs_internal(int fd, const char *_directory,
 						 const char *_mountpoint, fs_config_func_t fs_config_func, int gzip,
 						 int sparse, int crc, int wipe,
-						 struct selabel_handle *sehnd, int verbose, time_t fixed_time)
+						 struct selabel_handle *sehnd, int verbose, time_t fixed_time,
+						 FILE* block_list_file)
 {
 	u32 root_inode_num;
 	u16 root_mode;
@@ -592,7 +593,7 @@ int make_ext4fs_internal(int fd, const char *_directory,
 #else
 	if (directory)
 		root_inode_num = build_directory_structure(directory, mountpoint, 0,
-				fs_config_func, sehnd, verbose, fixed_time);
+			fs_config_func, sehnd, verbose, fixed_time);
 	else
 		root_inode_num = build_default_directory_structure(mountpoint, sehnd);
 #endif
@@ -621,6 +622,23 @@ int make_ext4fs_internal(int fd, const char *_directory,
 
 	ext4_queue_sb();
 
+	if (block_list_file) {
+		size_t dirlen = directory ? strlen(directory) : 0;
+		struct block_allocation* p = get_saved_allocation_chain();
+		while (p) {
+			if (directory && strncmp(p->filename, directory, dirlen) == 0) {
+				// substitute mountpoint for the leading directory in the filename, in the output file
+				fprintf(block_list_file, "%s%s", mountpoint, p->filename + dirlen);
+			} else {
+				fprintf(block_list_file, "%s", p->filename);
+			}
+			print_blocks(block_list_file, p);
+			struct block_allocation* pn = p->next;
+			free_alloc(p);
+			p = pn;
+		}
+	}
+
 	printf("Created filesystem with %d/%d inodes and %d/%d blocks\n",
 			aux_info.sb->s_inodes_count - aux_info.sb->s_free_inodes_count,
 			aux_info.sb->s_inodes_count,
diff --git a/ext4_utils/make_ext4fs_main.c b/ext4_utils/make_ext4fs_main.c
index 87eaecd7..a6c5f616 100644
--- a/ext4_utils/make_ext4fs_main.c
+++ b/ext4_utils/make_ext4fs_main.c
@@ -54,7 +54,7 @@ static void usage(char *path)
 	fprintf(stderr, "    [ -g <blocks per group> ] [ -i <inodes> ] [ -I <inode size> ]\n");
 	fprintf(stderr, "    [ -L <label> ] [ -f ] [ -a <android mountpoint> ]\n");
 	fprintf(stderr, "    [ -S file_contexts ] [ -C fs_config ] [ -T timestamp ]\n");
-	fprintf(stderr, "    [ -z | -s ] [ -w ] [ -c ] [ -J ] [ -v ]\n");
+	fprintf(stderr, "    [ -z | -s ] [ -w ] [ -c ] [ -J ] [ -v ] [ -B <block_list_file> ]\n");
 	fprintf(stderr, "    <filename> [<directory>]\n");
 }
 
@@ -75,11 +75,12 @@ int main(int argc, char **argv)
 	int verbose = 0;
 	time_t fixed_time = -1;
 	struct selabel_handle *sehnd = NULL;
+	FILE* block_list_file = NULL;
 #ifndef USE_MINGW
 	struct selinux_opt seopts[] = { { SELABEL_OPT_PATH, "" } };
 #endif
 
-	while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:S:T:C:fwzJsctv")) != -1) {
+	while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:S:T:C:B:fwzJsctv")) != -1) {
 		switch (opt) {
 		case 'l':
 			info.len = parse_num(optarg);
@@ -151,6 +152,13 @@ int main(int argc, char **argv)
 		case 'C':
 			fs_config_file = optarg;
 			break;
+		case 'B':
+			block_list_file = fopen(optarg, "w");
+			if (block_list_file == NULL) {
+				fprintf(stderr, "failed to open block_list_file: %s\n", strerror(errno));
+				exit(EXIT_FAILURE);
+			}
+			break;
 		default: /* '?' */
 			usage(argv[0]);
 			exit(EXIT_FAILURE);
@@ -219,8 +227,10 @@ int main(int argc, char **argv)
 	}
 
 	exitcode = make_ext4fs_internal(fd, directory, mountpoint, fs_config_func, gzip,
-			sparse, crc, wipe, sehnd, verbose, fixed_time);
+		sparse, crc, wipe, sehnd, verbose, fixed_time, block_list_file);
 	close(fd);
+	if (block_list_file)
+		fclose(block_list_file);
 	if (exitcode && strcmp(filename, "-"))
 		unlink(filename);
 	return exitcode;
diff --git a/ext4_utils/mkuserimg.sh b/ext4_utils/mkuserimg.sh
index d32eadbc..c8b83e0a 100755
--- a/ext4_utils/mkuserimg.sh
+++ b/ext4_utils/mkuserimg.sh
@@ -5,7 +5,8 @@
 function usage() {
 cat<<EOT
 Usage:
-mkuserimg.sh [-s] SRC_DIR OUTPUT_FILE EXT_VARIANT MOUNT_POINT SIZE [-T TIMESTAMP] [-C FS_CONFIG] [FILE_CONTEXTS]
+mkuserimg.sh [-s] SRC_DIR OUTPUT_FILE EXT_VARIANT MOUNT_POINT SIZE
+             [-T TIMESTAMP] [-C FS_CONFIG] [-B BLOCK_LIST_FILE] [FILE_CONTEXTS]
 EOT
 }
 
@@ -44,6 +45,12 @@ if [[ "$1" == "-C" ]]; then
   shift; shift
 fi
 
+BLOCK_LIST=
+if [[ "$1" == "-B" ]]; then
+  BLOCK_LIST=$2
+  shift; shift
+fi
+
 FC=$1
 
 case $EXT_VARIANT in
@@ -68,6 +75,9 @@ fi
 if [ -n "$FS_CONFIG" ]; then
   OPT="$OPT -C $FS_CONFIG"
 fi
+if [ -n "$BLOCK_LIST" ]; then
+  OPT="$OPT -B $BLOCK_LIST"
+fi
 
 MAKE_EXT4FS_CMD="make_ext4fs $ENABLE_SPARSE_IMAGE -T $TIMESTAMP $OPT -l $SIZE -a $MOUNT_POINT $OUTPUT_FILE $SRC_DIR"
 echo $MAKE_EXT4FS_CMD