AOSP: e2fsdroid: Refactor block_range.

block_range is a singly-linked list, but the head/tail links are
manually managed all over. Instead, introduce a block_range_list
structure and refactor list helpers to operate on this instead. This
ensures head/tail are maintained properly (in some cases, like
delete_block_range, they were not).

Bug: 145316683
Test: manual test
Change-Id: Ieec6324549e2c3a71129871f703f4f0a37aeb1fa
From AOSP commit: 4220594792297619d2e70a29476667d1698dbd63

6 files changed, 74 insertions, 61 deletions

diff --git a/contrib/android/base_fs.c b/contrib/android/base_fs.c
index 14203050..652317e2 100644
--- a/contrib/android/base_fs.c
+++ b/contrib/android/base_fs.c
@@ -72,8 +72,7 @@ static struct basefs_entry *basefs_readline(FILE *f, const char *mountpoint,
 		range_start = atoll(block);
 		block = strtok_r(NULL, "-", &saveptr2);
 		range_end = block ? atoll(block) : range_start;
-		add_blocks_to_range(&entry->head, &entry->tail, range_start,
-				    range_end);
+		add_blocks_to_range(&entry->blocks, range_start, range_end);
 		block_range = strtok_r(NULL, ",\n", &saveptr1);
 	}
 end:
@@ -151,7 +150,6 @@ static int start_new_file(char *path, ext2_ino_t ino EXT2FS_ATTR((unused)),
 {
 	struct base_fs *params = data;
 
-	params->entry.head = params->entry.tail = NULL;
 	params->entry.path = LINUX_S_ISREG(inode->i_mode) ? path : NULL;
 	return 0;
 }
@@ -162,8 +160,7 @@ static int add_block(ext2_filsys fs EXT2FS_ATTR((unused)), blk64_t blocknr,
 	struct base_fs *params = data;
 
 	if (params->entry.path && !metadata)
-		add_blocks_to_range(&params->entry.head, &params->entry.tail,
-				    blocknr, blocknr);
+		add_blocks_to_range(&params->entry.blocks, blocknr, blocknr);
 	return 0;
 }
 
@@ -181,11 +178,11 @@ static int end_new_file(void *data)
 		return 0;
 	if (fprintf(params->file, "%s%s ", params->mountpoint,
 		    params->entry.path) < 0
-	    || write_block_ranges(params->file, params->entry.head, ",")
+	    || write_block_ranges(params->file, params->entry.blocks.head, ",")
 	    || fwrite("\n", 1, 1, params->file) != 1)
 		return -1;
 
-	delete_block_ranges(params->entry.head);
+	delete_block_ranges(&params->entry.blocks);
 	return 0;
 }
 
diff --git a/contrib/android/base_fs.h b/contrib/android/base_fs.h
index e9f46b4a..f53f1ed8 100644
--- a/contrib/android/base_fs.h
+++ b/contrib/android/base_fs.h
@@ -7,8 +7,7 @@
 
 struct basefs_entry {
 	char *path;
-	struct block_range *head;
-	struct block_range *tail;
+	struct block_range_list blocks;
 };
 
 extern struct fsmap_format base_fs_format;
diff --git a/contrib/android/basefs_allocator.c b/contrib/android/basefs_allocator.c
index a014744a..474cc03b 100644
--- a/contrib/android/basefs_allocator.c
+++ b/contrib/android/basefs_allocator.c
@@ -13,8 +13,11 @@ struct base_fs_allocator {
 static errcode_t basefs_block_allocator(ext2_filsys, blk64_t, blk64_t *,
 					struct blk_alloc_ctx *ctx);
 
-static void fs_free_blocks_range(ext2_filsys fs, struct block_range *blocks)
+static void fs_free_blocks_range(ext2_filsys fs,
+				 struct block_range_list *list)
 {
+	struct block_range *blocks = list->head;
+
 	while (blocks) {
 		ext2fs_unmark_block_bitmap_range2(fs->block_map, blocks->start,
 			blocks->end - blocks->start + 1);
@@ -22,8 +25,10 @@ static void fs_free_blocks_range(ext2_filsys fs, struct block_range *blocks)
 	}
 }
 
-static void fs_reserve_blocks_range(ext2_filsys fs, struct block_range *blocks)
+static void fs_reserve_blocks_range(ext2_filsys fs,
+				    struct block_range_list *list)
 {
+	struct block_range *blocks = list->head;
 	while (blocks) {
 		ext2fs_mark_block_bitmap_range2(fs->block_map,
 			blocks->start, blocks->end - blocks->start + 1);
@@ -50,7 +55,7 @@ errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file,
 	if (retval)
 		goto err_bitmap;
 	while ((e = ext2fs_hashmap_iter_in_order(entries, &it)))
-		fs_reserve_blocks_range(fs, e->head);
+		fs_reserve_blocks_range(fs, &e->blocks);
 
 	allocator->cur_entry = NULL;
 	allocator->entries = entries;
@@ -72,19 +77,12 @@ static errcode_t basefs_block_allocator(ext2_filsys fs, blk64_t goal,
 					blk64_t *ret, struct blk_alloc_ctx *ctx)
 {
 	errcode_t retval;
-	struct block_range *next_range;
 	struct base_fs_allocator *allocator = fs->priv_data;
 	struct basefs_entry *e = allocator->cur_entry;
 
 	/* Try to get a block from the base_fs */
-	if (e && e->head && ctx && (ctx->flags & BLOCK_ALLOC_DATA)) {
-		*ret = e->head->start;
-		e->head->start += 1;
-		if (e->head->start > e->head->end) {
-			next_range = e->head->next;
-			free(e->head);
-			e->head = next_range;
-		}
+	if (e && e->blocks.head && ctx && (ctx->flags & BLOCK_ALLOC_DATA)) {
+		*ret = consume_next_block(&e->blocks);
 	} else { /* Allocate a new block */
 		retval = ext2fs_new_block2(fs, goal, fs->block_map, ret);
 		if (retval)
@@ -101,9 +99,8 @@ void base_fs_alloc_cleanup(ext2_filsys fs)
 	struct base_fs_allocator *allocator = fs->priv_data;
 
 	while ((e = ext2fs_hashmap_iter_in_order(allocator->entries, &it))) {
-		fs_free_blocks_range(fs, e->head);
-		delete_block_ranges(e->head);
-		e->head = e->tail = NULL;
+		fs_free_blocks_range(fs, &e->blocks);
+		delete_block_ranges(&e->blocks);
 	}
 
 	fs->priv_data = NULL;
@@ -140,9 +137,7 @@ errcode_t base_fs_alloc_unset_target(ext2_filsys fs,
 	if (!allocator || !allocator->cur_entry || mode != S_IFREG)
 		return 0;
 
-	fs_free_blocks_range(fs, allocator->cur_entry->head);
-	delete_block_ranges(allocator->cur_entry->head);
-	allocator->cur_entry->head = allocator->cur_entry->tail = NULL;
-	allocator->cur_entry = NULL;
+	fs_free_blocks_range(fs, &allocator->cur_entry->blocks);
+	delete_block_ranges(&allocator->cur_entry->blocks);
 	return 0;
 }
diff --git a/contrib/android/block_list.c b/contrib/android/block_list.c
index 25dcc514..63cc1a22 100644
--- a/contrib/android/block_list.c
+++ b/contrib/android/block_list.c
@@ -9,16 +9,13 @@ struct block_list {
 	FILE *f;
 	const char *mountpoint;
 
-	struct {
-		const char *filename;
-		struct block_range *head;
-		struct block_range *tail;
-	} entry;
+	const char *filename;
+	struct block_range_list blocks;
 };
 
 static void *init(const char *file, const char *mountpoint)
 {
-	struct block_list *params = malloc(sizeof(*params));
+	struct block_list *params = calloc(1, sizeof(*params));
 
 	if (!params)
 		return NULL;
@@ -37,8 +34,7 @@ static int start_new_file(char *path, ext2_ino_t ino EXT2FS_ATTR((unused)),
 {
 	struct block_list *params = data;
 
-	params->entry.head = params->entry.tail = NULL;
-	params->entry.filename = LINUX_S_ISREG(inode->i_mode) ? path : NULL;
+	params->filename = LINUX_S_ISREG(inode->i_mode) ? path : NULL;
 	return 0;
 }
 
@@ -47,9 +43,8 @@ static int add_block(ext2_filsys fs EXT2FS_ATTR((unused)), blk64_t blocknr,
 {
 	struct block_list *params = data;
 
-	if (params->entry.filename && !metadata)
-		add_blocks_to_range(&params->entry.head, &params->entry.tail,
-				    blocknr, blocknr);
+	if (params->filename && !metadata)
+		add_blocks_to_range(&params->blocks, blocknr, blocknr);
 	return 0;
 }
 
@@ -63,15 +58,15 @@ static int end_new_file(void *data)
 {
 	struct block_list *params = data;
 
-	if (!params->entry.filename || !params->entry.head)
+	if (!params->filename || !params->blocks.head)
 		return 0;
 	if (fprintf(params->f, "%s%s ", params->mountpoint,
-		    params->entry.filename) < 0
-	    || write_block_ranges(params->f, params->entry.head, " ")
+		    params->filename) < 0
+	    || write_block_ranges(params->f, params->blocks.head, " ")
 	    || fwrite("\n", 1, 1, params->f) != 1)
 		return -1;
 
-	delete_block_ranges(params->entry.head);
+	delete_block_ranges(&params->blocks);
 	return 0;
 }
 
diff --git a/contrib/android/block_range.c b/contrib/android/block_range.c
index 2f951c78..0a068826 100644
--- a/contrib/android/block_range.c
+++ b/contrib/android/block_range.c
@@ -12,29 +12,35 @@ struct block_range *new_block_range(blk64_t start, blk64_t end)
 	return range;
 }
 
-void add_blocks_to_range(struct block_range **head, struct block_range **tail,
-			 blk64_t blk_start, blk64_t blk_end)
+void add_blocks_to_range(struct block_range_list *list, blk64_t blk_start,
+			 blk64_t blk_end)
 {
-	if (*head == NULL)
-		*head = *tail = new_block_range(blk_start, blk_end);
-	else if ((*tail)->end + 1 == blk_start)
-		(*tail)->end += (blk_end - blk_start + 1);
+	if (list->head == NULL)
+		list->head = list->tail = new_block_range(blk_start, blk_end);
+	else if (list->tail->end + 1 == blk_start)
+		list->tail->end += (blk_end - blk_start + 1);
 	else {
 		struct block_range *range = new_block_range(blk_start, blk_end);
-		(*tail)->next = range;
-		*tail = range;
+		list->tail->next = range;
+		list->tail = range;
 	}
 }
 
-void delete_block_ranges(struct block_range *head)
+static void remove_head(struct block_range_list *list)
 {
-	struct block_range *tmp;
+	struct block_range *next_range = list->head->next;
 
-	while (head) {
-		tmp = head->next;
-		free(head);
-		head = tmp;
-	}
+	free(list->head);
+	if (next_range == NULL)
+		list->head = list->tail = NULL;
+	else
+		list->head = next_range;
+}
+
+void delete_block_ranges(struct block_range_list *list)
+{
+	while (list->head)
+		remove_head(list);
 }
 
 int write_block_ranges(FILE *f, struct block_range *range,
@@ -62,3 +68,13 @@ int write_block_ranges(FILE *f, struct block_range *range,
 		return -1;
 	return 0;
 }
+
+blk64_t consume_next_block(struct block_range_list *list)
+{
+	blk64_t ret = list->head->start;
+
+	list->head->start += 1;
+	if (list->head->start > list->head->end)
+		remove_head(list);
+	return ret;
+}
diff --git a/contrib/android/block_range.h b/contrib/android/block_range.h
index 31e3c23f..cf7971e8 100644
--- a/contrib/android/block_range.h
+++ b/contrib/android/block_range.h
@@ -10,9 +10,20 @@ struct block_range {
 	struct block_range *next;
 };
 
-void add_blocks_to_range(struct block_range **head, struct block_range **tail,
-			 blk64_t blk_start, blk64_t blk_end);
-void delete_block_ranges(struct block_range *head);
+struct block_range_list {
+	struct block_range *head;
+	struct block_range *tail;
+};
+
+void add_blocks_to_range(struct block_range_list *list, blk64_t blk_start,
+			 blk64_t blk_end);
+void delete_block_ranges(struct block_range_list *list);
 int write_block_ranges(FILE *f, struct block_range *range, char *sep);
 
+/*
+ * Given a non-empty range list, return the next block and remove it from the
+ * list.
+ */
+blk64_t consume_next_block(struct block_range_list *list);
+
 #endif /* !BLOCK_RANGE_H */