Redesign make_ext4fs to incrementally generate ext4 images

Allows passing a base fs mapping file through -d which preserves the
location of those mapping in existing files

Internal Design Doc: go/incremental-ext4
BUG: 26839493
Change-Id: I05e296693429d39466d257d1d0a3daf00510dc26
Signed-off-by: Mohamad Ayyash <mkayyash@google.com>

8 files changed, 419 insertions, 130 deletions

diff --git a/ext4_utils/allocate.c b/ext4_utils/allocate.c
index d18aec56..2118c277 100644
--- a/ext4_utils/allocate.c
+++ b/ext4_utils/allocate.c
@@ -5,7 +5,7 @@
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
- *      http://www.apache.org/licenses/LICENSE-2.0
+ *	  http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
@@ -22,31 +22,6 @@
 #include <stdio.h>
 #include <stdlib.h>
 
-struct region {
-	u32 block;
-	u32 len;
-	int bg;
-	struct region *next;
-	struct region *prev;
-};
-
-struct block_group_info {
-	u32 first_block;
-	int header_blocks;
-	int data_blocks_used;
-	int has_superblock;
-	u8 *bitmaps;
-	u8 *block_bitmap;
-	u8 *inode_bitmap;
-	u8 *inode_table;
-	u32 free_blocks;
-	u32 first_free_block;
-	u32 free_inodes;
-	u32 first_free_inode;
-	u16 flags;
-	u16 used_dirs;
-};
-
 struct xattr_list_element {
 	struct ext4_inode *inode;
 	struct ext4_xattr_header *header;
@@ -106,7 +81,7 @@ static void region_list_remove(struct region_list *list, struct region *reg)
 	reg->prev = NULL;
 }
 
-static void region_list_append(struct region_list *list, struct region *reg)
+void region_list_append(struct region_list *list, struct region *reg)
 {
 	if (list->first == NULL) {
 		list->first = reg;
@@ -141,15 +116,17 @@ static void dump_region_lists(struct block_allocation *alloc) {
 }
 #endif
 
-void print_blocks(FILE* f, struct block_allocation *alloc)
+void print_blocks(FILE* f, struct block_allocation *alloc, char separator)
 {
 	struct region *reg;
+	fputc(' ', f);
 	for (reg = alloc->list.first; reg; reg = reg->next) {
 		if (reg->len == 1) {
-			fprintf(f, " %d", reg->block);
+			fprintf(f, "%d", reg->block);
 		} else {
-			fprintf(f, " %d-%d", reg->block, reg->block + reg->len - 1);
+			fprintf(f, "%d-%d", reg->block, reg->block + reg->len - 1);
 		}
+		fputc(separator, f);
 	}
 	fputc('\n', f);
 }
@@ -210,45 +187,38 @@ static int reserve_blocks(struct block_group_info *bg, u32 start, u32 num)
 	unsigned int i = 0;
 
 	u32 block = start;
-	if (num > bg->free_blocks)
-		return -1;
-
 	for (i = 0; i < num && block % 8 != 0; i++, block++) {
 		if (bitmap_set_bit(bg->block_bitmap, block)) {
-			error("attempted to reserve already reserved block");
+			error("attempted to reserve already reserved block %d and num is %d", block, num);
 			return -1;
 		}
 	}
 
 	for (; i + 8 <= (num & ~7); i += 8, block += 8) {
 		if (bitmap_set_8_bits(bg->block_bitmap, block)) {
-			error("attempted to reserve already reserved block");
+			error("attempted to reserve already reserved block %d and num is %d", block, num);
 			return -1;
 		}
 	}
 
 	for (; i < num; i++, block++) {
 		if (bitmap_set_bit(bg->block_bitmap, block)) {
-			error("attempted to reserve already reserved block");
+			error("attempted to reserve already reserved block %d and num is %d", block, num);
 			return -1;
 		}
 	}
 
 	bg->free_blocks -= num;
-	if (start == bg->first_free_block)
-		bg->first_free_block = start + num;
 
 	return 0;
 }
 
-static void free_blocks(struct block_group_info *bg, u32 num_blocks)
+static void free_blocks(struct block_group_info *bg, u32 block, u32 num_blocks)
 {
 	unsigned int i;
-	u32 block = bg->first_free_block - 1;
 	for (i = 0; i < num_blocks; i++, block--)
 		bg->block_bitmap[block / 8] &= ~(1 << (block % 8));
 	bg->free_blocks += num_blocks;
-	bg->first_free_block -= num_blocks;
 }
 
 /* Reduces an existing allocation by len blocks by return the last blocks
@@ -258,14 +228,15 @@ void reduce_allocation(struct block_allocation *alloc, u32 len)
 {
 	while (len) {
 		struct region *last_reg = alloc->list.last;
+		struct block_group_info *bg = &aux_info.bgs[last_reg->bg];
 
 		if (last_reg->len > len) {
-			free_blocks(&aux_info.bgs[last_reg->bg], len);
+			free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, len);
 			last_reg->len -= len;
 			len = 0;
 		} else {
 			struct region *reg = alloc->list.last->prev;
-			free_blocks(&aux_info.bgs[last_reg->bg], last_reg->len);
+			free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, last_reg->len);
 			len -= last_reg->len;
 			if (reg) {
 				reg->next = NULL;
@@ -304,18 +275,28 @@ static void init_bg(struct block_group_info *bg, unsigned int i)
 
 	bg->data_blocks_used = 0;
 	bg->free_blocks = info.blocks_per_group;
-	bg->first_free_block = 0;
 	bg->free_inodes = info.inodes_per_group;
 	bg->first_free_inode = 1;
 	bg->flags = 0;
 
-	if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0)
+	bg->chunk_count = 0;
+	bg->max_chunk_count = 1;
+	bg->chunks = (struct region*) calloc(bg->max_chunk_count, sizeof(struct region));
+
+	if (reserve_blocks(bg, 0, bg->header_blocks) < 0)
 		error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i);
+	// Add empty starting delimiter chunk
+	reserve_bg_chunk(i, bg->header_blocks, 0);
 
 	if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) {
 		u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks;
 		reserve_blocks(bg, info.blocks_per_group - overrun, overrun);
+		// Add empty ending delimiter chunk
+		reserve_bg_chunk(i, info.blocks_per_group - overrun, 0);
+	} else {
+		reserve_bg_chunk(i, info.blocks_per_group - 1, 0);
 	}
+
 }
 
 void block_allocator_init()
@@ -341,73 +322,79 @@ void block_allocator_free()
 	free(aux_info.bgs);
 }
 
-static u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num)
-{
-	if (get_free_blocks(bg_num) < len)
-		return EXT4_ALLOCATE_FAILED;
-
-	u32 block = aux_info.bgs[bg_num].first_free_block;
-	struct block_group_info *bg = &aux_info.bgs[bg_num];
-	if (reserve_blocks(bg, bg->first_free_block, len) < 0) {
-		error("failed to reserve %u blocks in block group %u\n", len, bg_num);
-		return EXT4_ALLOCATE_FAILED;
-	}
-
-	aux_info.bgs[bg_num].data_blocks_used += len;
-
-	return bg->first_block + block;
-}
-
 /* Allocate a single block and return its block number */
 u32 allocate_block()
 {
-	unsigned int i;
-	for (i = 0; i < aux_info.groups; i++) {
-		u32 block = ext4_allocate_blocks_from_block_group(1, i);
-
-		if (block != EXT4_ALLOCATE_FAILED)
-			return block;
+	u32 block;
+	struct block_allocation *blk_alloc = allocate_blocks(1);
+	if (!blk_alloc) {
+		return EXT4_ALLOCATE_FAILED;
 	}
-
-	return EXT4_ALLOCATE_FAILED;
+	block = blk_alloc->list.first->block;
+	free_alloc(blk_alloc);
+	return block;
 }
 
 static struct region *ext4_allocate_best_fit_partial(u32 len)
 {
-	unsigned int i;
-	unsigned int found_bg = 0;
-	u32 found_bg_len = 0;
+	unsigned int i, j;
+	unsigned int found_bg = 0, found_prev_chunk = 0, found_block = 0;
+	u32 found_allocate_len = 0;
+	bool minimize = false;
+	struct block_group_info *bgs = aux_info.bgs;
+	struct region *reg;
 
 	for (i = 0; i < aux_info.groups; i++) {
-		u32 bg_len = aux_info.bgs[i].free_blocks;
-
-		if ((len <= bg_len && (found_bg_len == 0 || bg_len < found_bg_len)) ||
-		    (len > found_bg_len && bg_len > found_bg_len)) {
-			found_bg = i;
-			found_bg_len = bg_len;
+		for (j = 1; j < bgs[i].chunk_count; j++) {
+			u32 hole_start, hole_size;
+			hole_start = bgs[i].chunks[j-1].block + bgs[i].chunks[j-1].len;
+			hole_size =  bgs[i].chunks[j].block - hole_start;
+			if (hole_size == len) {
+				// Perfect fit i.e. right between 2 chunks no need to keep searching
+				found_bg = i;
+				found_prev_chunk = j - 1;
+				found_block = hole_start;
+				found_allocate_len = hole_size;
+				goto done;
+			} else if (hole_size > len && (found_allocate_len == 0 || (found_allocate_len > hole_size))) {
+				found_bg = i;
+				found_prev_chunk = j - 1;
+				found_block = hole_start;
+				found_allocate_len = hole_size;
+				minimize = true;
+			} else if (!minimize) {
+				if (found_allocate_len < hole_size) {
+					found_bg = i;
+					found_prev_chunk = j - 1;
+					found_block = hole_start;
+					found_allocate_len = hole_size;
+				}
+			}
 		}
 	}
 
-	if (found_bg_len) {
-		u32 allocate_len = min(len, found_bg_len);
-		struct region *reg;
-		u32 block = ext4_allocate_blocks_from_block_group(allocate_len, found_bg);
-		if (block == EXT4_ALLOCATE_FAILED) {
-			error("failed to allocate %d blocks in block group %d", allocate_len, found_bg);
-			return NULL;
-		}
-		reg = malloc(sizeof(struct region));
-		reg->block = block;
-		reg->len = allocate_len;
-		reg->next = NULL;
-		reg->prev = NULL;
-		reg->bg = found_bg;
-		return reg;
-	} else {
+	if (found_allocate_len == 0) {
 		error("failed to allocate %u blocks, out of space?", len);
+		return NULL;
 	}
-
-	return NULL;
+	if (found_allocate_len > len) found_allocate_len = len;
+done:
+	// reclaim allocated space in chunk
+	bgs[found_bg].chunks[found_prev_chunk].len += found_allocate_len;
+	if (reserve_blocks(&bgs[found_bg],
+				found_block,
+				found_allocate_len) < 0) {
+		error("failed to reserve %u blocks in block group %u\n", found_allocate_len, found_bg);
+		return NULL;
+	}
+	bgs[found_bg].data_blocks_used += found_allocate_len;
+	reg = malloc(sizeof(struct region));
+	reg->block = found_block + bgs[found_bg].first_block;
+	reg->len = found_allocate_len;
+	reg->next = NULL;
+	reg->prev = NULL;
+	reg->bg = found_bg;
+	return reg;
 }
 
 static struct region *ext4_allocate_best_fit(u32 len)
@@ -439,9 +426,9 @@ static struct region *ext4_allocate_best_fit(u32 len)
 /* Allocate len blocks.  The blocks may be spread across multiple block groups,
    and are returned in a linked list of the blocks in each block group.  The
    allocation algorithm is:
-      1.  If the remaining allocation is larger than any available contiguous region,
-          allocate the largest contiguous region and loop
-      2.  Otherwise, allocate the smallest contiguous region that it fits in
+	  1.  If the remaining allocation is larger than any available contiguous region,
+		  allocate the largest contiguous region and loop
+	  2.  Otherwise, allocate the smallest contiguous region that it fits in
 */
 struct block_allocation *allocate_blocks(u32 len)
 {
@@ -452,6 +439,8 @@ struct block_allocation *allocate_blocks(u32 len)
 
 	struct block_allocation *alloc = create_allocation();
 	alloc->list.first = reg;
+	while (reg->next != NULL)
+		reg = reg->next;
 	alloc->list.last = reg;
 	alloc->list.iter = alloc->list.first;
 	alloc->list.partial_iter = 0;
@@ -779,3 +768,34 @@ void free_alloc(struct block_allocation *alloc)
 
 	free(alloc);
 }
+
+void reserve_bg_chunk(int bg, u32 start_block, u32 size) {
+	struct block_group_info *bgs = aux_info.bgs;
+	int chunk_count;
+	if (bgs[bg].chunk_count == bgs[bg].max_chunk_count) {
+		bgs[bg].max_chunk_count *= 2;
+		bgs[bg].chunks = realloc(bgs[bg].chunks, bgs[bg].max_chunk_count * sizeof(struct region));
+		if (!bgs[bg].chunks)
+			critical_error("realloc failed");
+	}
+	chunk_count = bgs[bg].chunk_count;
+	bgs[bg].chunks[chunk_count].block = start_block;
+	bgs[bg].chunks[chunk_count].len = size;
+	bgs[bg].chunks[chunk_count].bg = bg;
+	bgs[bg].chunk_count++;
+}
+
+int reserve_blocks_for_allocation(struct block_allocation *alloc) {
+	struct region *reg;
+	struct block_group_info *bgs = aux_info.bgs;
+
+	if (!alloc) return 0;
+	reg = alloc->list.first;
+	while (reg != NULL) {
+		if (reserve_blocks(&bgs[reg->bg], reg->block - bgs[reg->bg].first_block, reg->len) < 0)
+			return -1;
+		reg = reg->next;
+	}
+	return 0;
+}
+
diff --git a/ext4_utils/allocate.h b/ext4_utils/allocate.h
index 5c26792c..cac543f5 100644
--- a/ext4_utils/allocate.h
+++ b/ext4_utils/allocate.h
@@ -5,7 +5,7 @@
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
- *      http://www.apache.org/licenses/LICENSE-2.0
+ *	  http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
@@ -21,7 +21,13 @@
 
 #include "ext4_utils.h"
 
-struct region;
+struct region {
+	u32 block;
+	u32 len;
+	int bg;
+	struct region *next;
+	struct region *prev;
+};
 
 struct region_list {
 	struct region *first;
@@ -37,6 +43,24 @@ struct block_allocation {
 	struct block_allocation* next;
 };
 
+struct block_group_info {
+	u32 first_block;
+	int header_blocks;
+	int data_blocks_used;
+	int has_superblock;
+	u8 *bitmaps;
+	u8 *block_bitmap;
+	u8 *inode_bitmap;
+	u8 *inode_table;
+	u32 free_blocks;
+	u32 free_inodes;
+	u32 first_free_inode;
+	u16 flags;
+	u16 used_dirs;
+	int chunk_count;
+	int max_chunk_count;
+	struct region *chunks;
+};
 
 void block_allocator_init();
 void block_allocator_free();
@@ -69,6 +93,8 @@ 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);
-
+void region_list_append(struct region_list *list, struct region *reg);
+void print_blocks(FILE* f, struct block_allocation *alloc, char separator);
+void reserve_bg_chunk(int bg, u32 start_block, u32 size);
+int reserve_blocks_for_allocation(struct block_allocation *alloc);
 #endif
diff --git a/ext4_utils/ext4_utils.c b/ext4_utils/ext4_utils.c
index 28f650d4..fba4f9fa 100644
--- a/ext4_utils/ext4_utils.c
+++ b/ext4_utils/ext4_utils.c
@@ -49,6 +49,7 @@ int force = 0;
 struct fs_info info;
 struct fs_aux_info aux_info;
 struct sparse_file *ext4_sparse_file;
+struct block_allocation *base_fs_allocations = NULL;
 
 jmp_buf setjmp_env;
 
diff --git a/ext4_utils/ext4_utils.h b/ext4_utils/ext4_utils.h
index 0159dbe2..0fbbdd31 100644
--- a/ext4_utils/ext4_utils.h
+++ b/ext4_utils/ext4_utils.h
@@ -119,6 +119,7 @@ struct fs_aux_info {
 extern struct fs_info info;
 extern struct fs_aux_info aux_info;
 extern struct sparse_file *ext4_sparse_file;
+extern struct block_allocation *base_fs_allocations;
 
 extern jmp_buf setjmp_env;
 
@@ -161,7 +162,7 @@ int make_ext4fs_internal(int fd, const char *directory, const char *_target_out_
 						 const char *mountpoint, fs_config_func_t fs_config_func, int gzip,
 						 int sparse, int crc, int wipe, int real_uuid,
 						 struct selabel_handle *sehnd, int verbose, time_t fixed_time,
-						 FILE* block_list_file);
+						 FILE* block_list_file, FILE* base_alloc_file_in, FILE* base_alloc_file_out);
 
 int read_ext(int fd, int verbose);
 
diff --git a/ext4_utils/extent.c b/ext4_utils/extent.c
index 1900b104..42ddd97d 100644
--- a/ext4_utils/extent.c
+++ b/ext4_utils/extent.c
@@ -5,7 +5,7 @@
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
- *      http://www.apache.org/licenses/LICENSE-2.0
+ *	  http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
@@ -72,23 +72,43 @@ static void extent_create_backing_file(struct block_allocation *alloc,
 }
 
 static struct block_allocation *do_inode_allocate_extents(
-	struct ext4_inode *inode, u64 len)
+	struct ext4_inode *inode, u64 len, struct block_allocation *prealloc)
 {
-	u32 block_len = DIV_ROUND_UP(len, info.block_size);
-	struct block_allocation *alloc = allocate_blocks(block_len + 1);
+	u32 block_len = DIV_ROUND_UP(len, info.block_size), prealloc_block_len;
+	struct block_allocation *alloc;
 	u32 extent_block = 0;
 	u32 file_block = 0;
 	struct ext4_extent *extent;
 	u64 blocks;
 
-	if (alloc == NULL) {
-		error("Failed to allocate %d blocks\n", block_len + 1);
-		return NULL;
+	if (!prealloc) {
+		alloc = allocate_blocks(block_len + 1);
+		if (alloc == NULL) {
+			error("Failed to allocate %d blocks\n", block_len + 1);
+			return NULL;
+		}
+	} else {
+		prealloc_block_len = block_allocation_len(prealloc);
+		if (block_len + 1 > prealloc_block_len) {
+			alloc = allocate_blocks(block_len + 1 - prealloc_block_len);
+			if (alloc == NULL) {
+				error("Failed to allocate %d blocks\n",
+						block_len + 1 - prealloc_block_len);
+				return NULL;
+			}
+			region_list_append(&prealloc->list, alloc->list.first);
+			free(alloc);
+		}
+		alloc = prealloc;
 	}
 
 	int allocation_len = block_allocation_num_regions(alloc);
 	if (allocation_len <= 3) {
 		reduce_allocation(alloc, 1);
+		// IMPORTANT: reduce_allocation may have changed allocation
+		// length, otherwise file corruption happens when fs thinks
+		// a block is missing from extent header.
+		allocation_len = block_allocation_num_regions(alloc);
 	} else {
 		reserve_oob_blocks(alloc, 1);
 		extent_block = get_oob_block(alloc, 0);
@@ -183,7 +203,7 @@ u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len,
 	struct block_allocation *alloc;
 	u8 *data = NULL;
 
-	alloc = do_inode_allocate_extents(inode, len);
+	alloc = do_inode_allocate_extents(inode, len, NULL);
 	if (alloc == NULL) {
 		error("failed to allocate extents for %"PRIu64" bytes", len);
 		return NULL;
@@ -205,9 +225,26 @@ u8 *inode_allocate_data_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;
+	struct block_allocation *alloc, *prealloc = base_fs_allocations, *prev_prealloc = NULL;
+	// TODO(mkayyash): base_fs_allocations is sorted by filename, consider
+	// storing it in an array and then binary searching for a filename match instead
+	while (prealloc && prealloc->filename != NULL) {
+		if (!strcmp(filename, prealloc->filename)) {
+			break;
+		}
+		prev_prealloc = prealloc;
+		prealloc = prealloc->next;
+	}
+	if (prealloc) {
+		if (!prev_prealloc) {
+			base_fs_allocations = base_fs_allocations->next;
+		} else {
+			prev_prealloc->next = prealloc->next;
+		}
+		prealloc->next = NULL;
+	}
 
-	alloc = do_inode_allocate_extents(inode, len);
+	alloc = do_inode_allocate_extents(inode, len, prealloc);
 	if (alloc == NULL) {
 		error("failed to allocate extents for %"PRIu64" bytes", len);
 		return NULL;
@@ -222,7 +259,7 @@ void inode_allocate_extents(struct ext4_inode *inode, u64 len)
 {
 	struct block_allocation *alloc;
 
-	alloc = do_inode_allocate_extents(inode, len);
+	alloc = do_inode_allocate_extents(inode, len, NULL);
 	if (alloc == NULL) {
 		error("failed to allocate extents for %"PRIu64" bytes", len);
 		return;
diff --git a/ext4_utils/make_ext4fs.c b/ext4_utils/make_ext4fs.c
index 913a40df..7752e6b9 100644
--- a/ext4_utils/make_ext4fs.c
+++ b/ext4_utils/make_ext4fs.c
@@ -5,7 +5,7 @@
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
- *      http://www.apache.org/licenses/LICENSE-2.0
+ *	  http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
@@ -79,6 +79,13 @@
 
 #endif
 
+#define MAX_PATH 4096
+#define MAX_BLK_MAPPING_STR 1000
+
+const int blk_file_major_ver = 1;
+const int blk_file_minor_ver = 0;
+const char *blk_file_header_fmt = "Base EXT4 version %d.%d";
+
 /* TODO: Not implemented:
    Allocating blocks in the same block group as the file inode
    Hash or binary tree directories
@@ -91,7 +98,7 @@ static int filter_dot(const struct dirent *d)
 }
 
 static u32 build_default_directory_structure(const char *dir_path,
-					     struct selabel_handle *sehnd)
+						 struct selabel_handle *sehnd)
 {
 	u32 inode;
 	u32 root_inode;
@@ -425,8 +432,8 @@ int make_ext4fs_sparse_fd_directory(int fd, long long len,
 	info.len = len;
 
 	return make_ext4fs_internal(fd, directory, NULL, mountpoint, NULL,
-	                            0, 1, 0, 0, 0,
-	                            sehnd, 0, -1, NULL);
+								0, 1, 0, 0, 0,
+								sehnd, 0, -1, NULL, NULL, NULL);
 }
 
 int make_ext4fs(const char *filename, long long len,
@@ -436,8 +443,8 @@ int make_ext4fs(const char *filename, long long len,
 }
 
 int make_ext4fs_directory(const char *filename, long long len,
-                          const char *mountpoint, struct selabel_handle *sehnd,
-                          const char *directory)
+						  const char *mountpoint, struct selabel_handle *sehnd,
+						  const char *directory)
 {
 	int fd;
 	int status;
@@ -452,8 +459,8 @@ int make_ext4fs_directory(const char *filename, long long len,
 	}
 
 	status = make_ext4fs_internal(fd, directory, NULL, mountpoint, NULL,
-	                              0, 0, 0, 1, 0,
-	                              sehnd, 0, -1, NULL);
+								  0, 0, 0, 1, 0,
+								  sehnd, 0, -1, NULL, NULL, NULL);
 	close(fd);
 
 	return status;
@@ -519,17 +526,158 @@ static char *canonicalize_rel_slashes(const char *str)
 	return canonicalize_slashes(str, false);
 }
 
+static int compare_chunks(const void* chunk1, const void* chunk2) {
+	struct region* c1 = (struct region*) chunk1;
+	struct region* c2 = (struct region*) chunk2;
+	return c1->block - c2->block;
+}
+
+static int get_block_group(u32 block) {
+	int i, group = 0;
+	for(i = 0; i < aux_info.groups; i++) {
+		if (block >= aux_info.bgs[i].first_block)
+			group = i;
+		else
+			break;
+	}
+	return group;
+}
+
+static void extract_base_fs_allocations(const char *directory, const char *mountpoint,
+										FILE* base_alloc_file_in) {
+#define err_msg "base file badly formatted"
+	// FORMAT Version 1.0: filename blk_mapping
+	const char *base_alloc_file_in_format = "%s %s";
+	const int base_file_format_param_count = 2;
+
+	char stored_file_name[MAX_PATH], real_file_name[MAX_PATH], file_map[MAX_BLK_MAPPING_STR];
+	struct block_allocation *fs_alloc;
+	struct block_group_info *bgs = aux_info.bgs;
+	int i, major_version = 0, minor_version = 0;
+	char *base_file_line = NULL;
+	size_t base_file_line_len = 0;
+
+	printf("[v%d.%d] Generating an Incremental EXT4 image\n",
+			blk_file_major_ver, blk_file_minor_ver);
+	if (base_fs_allocations == NULL)
+		base_fs_allocations = create_allocation();
+	fs_alloc = base_fs_allocations;
+
+	fscanf(base_alloc_file_in, blk_file_header_fmt, &major_version, &minor_version);
+	if (major_version == 0) {
+		critical_error("Invalid base file");
+	}
+
+	if (major_version != blk_file_major_ver) {
+		critical_error("Incompatible base file: version required is %d.X",
+				blk_file_major_ver);
+	}
+
+	if (minor_version < blk_file_minor_ver) {
+		critical_error("Incompatible base file: version required is %d.%d or above",
+				blk_file_major_ver, blk_file_minor_ver);
+	}
+
+	while (getline(&base_file_line, &base_file_line_len, base_alloc_file_in) != -1) {
+		if (sscanf(base_file_line, base_alloc_file_in_format, &stored_file_name, &file_map)
+				!= base_file_format_param_count) {
+			continue;
+		}
+		if (strlen(stored_file_name) < strlen(mountpoint)) {
+			continue;
+		}
+		snprintf(real_file_name, MAX_PATH, "%s%s", directory, stored_file_name + strlen(mountpoint));
+		if (!access(real_file_name, R_OK)) {
+			char *block_range, *end_string;
+			int real_file_fd;
+			u32 start_block, end_block, block_file_size;
+			u32 real_file_block_size;
+
+			real_file_fd = open(real_file_name, O_RDONLY);
+			if (real_file_fd == -1) {
+				critical_error(err_msg);
+			}
+			real_file_block_size = get_file_size(real_file_fd);
+			close(real_file_fd);
+			real_file_block_size = DIV_ROUND_UP(real_file_block_size, info.block_size);
+			fs_alloc->filename = strdup(real_file_name);
+			block_range = strtok_r(file_map, ",", &end_string);
+			while (block_range && real_file_block_size) {
+				int block_group;
+				char *range, *end_token = NULL;
+				range = strtok_r(block_range, "-", &end_token);
+				if (!range) {
+					critical_error(err_msg);
+				}
+				start_block = parse_num(range);
+				range = strtok_r(NULL, "-", &end_token);
+				if (!range) {
+					end_block = start_block;
+				} else {
+					end_block = parse_num(range);
+				}
+				block_file_size = end_block - start_block + 1;
+				if (block_file_size > real_file_block_size) {
+					block_file_size = real_file_block_size;
+				}
+				// Assummption is that allocations are within the same block group
+				block_group = get_block_group(start_block);
+				if (block_group != get_block_group(end_block)) {
+					critical_error("base file allocation's end block is in a different "
+								   "block group than start block. did you change fs params?");
+				}
+				block_range = strtok_r(NULL, ",", &end_string);
+				append_region(fs_alloc, start_block, block_file_size, block_group);
+				reserve_bg_chunk(block_group, start_block - bgs[block_group].first_block, block_file_size);
+				real_file_block_size -= block_file_size;
+			}
+			if (reserve_blocks_for_allocation(fs_alloc) < 0)
+				critical_error("failed to reserve base fs allocation");
+			fs_alloc->next = create_allocation();
+			fs_alloc = fs_alloc->next;
+		}
+	}
+
+	for (i = 0; i < aux_info.groups; i++) {
+		qsort(bgs[i].chunks, bgs[i].chunk_count, sizeof(struct region), compare_chunks);
+	}
+
+	free(base_file_line);
+
+#undef err_msg
+}
+
+void generate_base_alloc_file_out(FILE* base_alloc_file_out, char* dir, char* mountpoint,
+								  struct block_allocation* p)
+{
+	size_t dirlen = dir ? strlen(dir) : 0;
+	fprintf(base_alloc_file_out, blk_file_header_fmt, blk_file_major_ver, blk_file_minor_ver);
+	fputc('\n', base_alloc_file_out);
+	while (p) {
+		if (dir && strncmp(p->filename, dir, dirlen) == 0) {
+			// substitute mountpoint for the leading directory in the filename, in the output file
+			fprintf(base_alloc_file_out, "%s%s", mountpoint, p->filename + dirlen);
+		} else {
+			fprintf(base_alloc_file_out, "%s", p->filename);
+		}
+		print_blocks(base_alloc_file_out, p, ',');
+		struct block_allocation* pn = p->next;
+		p = pn;
+	}
+}
+
 int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out_directory,
 						 const char *_mountpoint, fs_config_func_t fs_config_func, int gzip,
 						 int sparse, int crc, int wipe, int real_uuid,
 						 struct selabel_handle *sehnd, int verbose, time_t fixed_time,
-						 FILE* block_list_file)
+						 FILE* block_list_file, FILE* base_alloc_file_in, FILE* base_alloc_file_out)
 {
 	u32 root_inode_num;
 	u16 root_mode;
 	char *mountpoint;
 	char *directory = NULL;
 	char *target_out_directory = NULL;
+	struct block_allocation* p;
 
 	if (setjmp(setjmp_env))
 		return EXIT_FAILURE; /* Handle a call to longjmp() */
@@ -627,6 +775,9 @@ int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out
 
 	ext4_fill_in_sb(real_uuid);
 
+	if (base_alloc_file_in) {
+		extract_base_fs_allocations(directory, mountpoint, base_alloc_file_in);
+	}
 	if (reserve_inodes(0, 10) == EXT4_ALLOCATE_FAILED)
 		error("failed to reserve first 10 inodes");
 
@@ -670,6 +821,8 @@ int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out
 
 	ext4_update_free();
 
+	// TODO: Consider migrating the OTA tools to the new base alloc file format
+	// used for generating incremental images (see go/incremental-ext4)
 	if (block_list_file) {
 		size_t dirlen = directory ? strlen(directory) : 0;
 		struct block_allocation* p = get_saved_allocation_chain();
@@ -680,13 +833,17 @@ int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out
 			} else {
 				fprintf(block_list_file, "%s", p->filename);
 			}
-			print_blocks(block_list_file, p);
+			print_blocks(block_list_file, p, ' ');
 			struct block_allocation* pn = p->next;
-			free_alloc(p);
 			p = pn;
 		}
 	}
 
+	if (base_alloc_file_out) {
+		struct block_allocation* p = get_saved_allocation_chain();
+		generate_base_alloc_file_out(base_alloc_file_out, directory, mountpoint, p);
+	}
+
 	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,
@@ -702,6 +859,13 @@ int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out
 	sparse_file_destroy(ext4_sparse_file);
 	ext4_sparse_file = NULL;
 
+	p = get_saved_allocation_chain();
+	while (p) {
+		struct block_allocation* pn = p->next;
+		free_alloc(p);
+		p = pn;
+	}
+
 	free(mountpoint);
 	free(directory);
 
diff --git a/ext4_utils/make_ext4fs_main.c b/ext4_utils/make_ext4fs_main.c
index 03872db6..56ced5b5 100644
--- a/ext4_utils/make_ext4fs_main.c
+++ b/ext4_utils/make_ext4fs_main.c
@@ -57,6 +57,7 @@ static void usage(char *path)
 	fprintf(stderr, "    [ -L <label> ] [ -f ] [ -a <android mountpoint> ] [ -u ]\n");
 	fprintf(stderr, "    [ -S file_contexts ] [ -C fs_config ] [ -T timestamp ]\n");
 	fprintf(stderr, "    [ -z | -s ] [ -w ] [ -c ] [ -J ] [ -v ] [ -B <block_list_file> ]\n");
+	fprintf(stderr, "    [ -d <base_alloc_file_in> ] [ -D <base_alloc_file_out> ]\n");
 	fprintf(stderr, "    <filename> [[<directory>] <target_out_directory>]\n");
 }
 
@@ -80,11 +81,13 @@ int main(int argc, char **argv)
 	time_t fixed_time = -1;
 	struct selabel_handle *sehnd = NULL;
 	FILE* block_list_file = NULL;
+	FILE* base_alloc_file_in = NULL;
+	FILE* base_alloc_file_out = 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:B:fwzJsctvu")) != -1) {
+	while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:S:T:C:B:d:D:fwzJsctvu")) != -1) {
 		switch (opt) {
 		case 'l':
 			info.len = parse_num(optarg);
@@ -166,6 +169,20 @@ int main(int argc, char **argv)
 				exit(EXIT_FAILURE);
 			}
 			break;
+		case 'd':
+			base_alloc_file_in = fopen(optarg, "r");
+			if (base_alloc_file_in == NULL) {
+				fprintf(stderr, "failed to open base_alloc_file_in: %s\n", strerror(errno));
+				exit(EXIT_FAILURE);
+			}
+			break;
+		case 'D':
+			base_alloc_file_out = fopen(optarg, "w");
+			if (base_alloc_file_out == NULL) {
+				fprintf(stderr, "failed to open base_alloc_file_out: %s\n", strerror(errno));
+				exit(EXIT_FAILURE);
+			}
+			break;
 		default: /* '?' */
 			usage(argv[0]);
 			exit(EXIT_FAILURE);
@@ -237,10 +254,15 @@ int main(int argc, char **argv)
 	}
 
 	exitcode = make_ext4fs_internal(fd, directory, target_out_directory, mountpoint, fs_config_func, gzip,
-		sparse, crc, wipe, real_uuid, sehnd, verbose, fixed_time, block_list_file);
+		sparse, crc, wipe, real_uuid, sehnd, verbose, fixed_time,
+		block_list_file, base_alloc_file_in, base_alloc_file_out);
 	close(fd);
 	if (block_list_file)
 		fclose(block_list_file);
+	if (base_alloc_file_out)
+		fclose(base_alloc_file_out);
+	if (base_alloc_file_in)
+		fclose(base_alloc_file_in);
 	if (exitcode && strcmp(filename, "-"))
 		unlink(filename);
 	return exitcode;
diff --git a/ext4_utils/mkuserimg.sh b/ext4_utils/mkuserimg.sh
index 8667013e..b79baf98 100755
--- a/ext4_utils/mkuserimg.sh
+++ b/ext4_utils/mkuserimg.sh
@@ -6,7 +6,7 @@ function usage() {
 cat<<EOT
 Usage:
 mkuserimg.sh [-s] SRC_DIR OUTPUT_FILE EXT_VARIANT MOUNT_POINT SIZE [-j <journal_size>]
-             [-T TIMESTAMP] [-C FS_CONFIG] [-D PRODUCT_OUT] [-B BLOCK_LIST_FILE] [-L LABEL] [FILE_CONTEXTS]
+             [-T TIMESTAMP] [-C FS_CONFIG] [-D PRODUCT_OUT] [-B BLOCK_LIST_FILE] [-d BASE_ALLOC_FILE_IN ] [-A BASE_ALLOC_FILE_OUT ] [-L LABEL] [FILE_CONTEXTS]
 EOT
 }
 
@@ -67,6 +67,18 @@ if [[ "$1" == "-B" ]]; then
   shift; shift
 fi
 
+BASE_ALLOC_FILE_IN=
+if [[ "$1" == "-d" ]]; then
+  BASE_ALLOC_FILE_IN=$2
+  shift; shift
+fi
+
+BASE_ALLOC_FILE_OUT=
+if [[ "$1" == "-A" ]]; then
+  BASE_ALLOC_FILE_OUT=$2
+  shift; shift
+fi
+
 LABEL=
 if [[ "$1" == "-L" ]]; then
   LABEL=$2
@@ -100,6 +112,12 @@ fi
 if [ -n "$BLOCK_LIST" ]; then
   OPT="$OPT -B $BLOCK_LIST"
 fi
+if [ -n "$BASE_ALLOC_FILE_IN" ]; then
+  OPT="$OPT -d $BASE_ALLOC_FILE_IN"
+fi
+if [ -n "$BASE_ALLOC_FILE_OUT" ]; then
+  OPT="$OPT -D $BASE_ALLOC_FILE_OUT"
+fi
 if [ -n "$LABEL" ]; then
   OPT="$OPT -L $LABEL"
 fi