AOSP: e2fsdroid: create incremental images

Add an option to read a base_fs file and allocate the blocks according
to the mapping provided by the file.

Test: 1/ Create a normal image and an incremental one.
         Compare the number of blocks that have changed.
      2/ Create an image.
         Create an incremantal image.
         The basefs file and the block_list file are the same.

Change-Id: Ie000ca48cf000d95e7a45a9752699abfc7484b6c
From AOSP commit: 16babe7b79c4c9b6d75d60e30c04a8e24278e4fa

Signed-off-by: Theodore Ts'o <tytso@mit.edu>

8 files changed, 439 insertions, 9 deletions

diff --git a/contrib/android/Android.mk b/contrib/android/Android.mk
index ac128578..f2216912 100644
--- a/contrib/android/Android.mk
+++ b/contrib/android/Android.mk
@@ -5,11 +5,15 @@ e2fsdroid_src := e2fsdroid.c \
     fsmap.c \
     block_list.c \
     base_fs.c \
-    perms.c
+    perms.c \
+    basefs_allocator.c \
+    hashmap.c \
+    ../../misc/create_inode.c
 
 include $(CLEAR_VARS)
 LOCAL_SRC_FILES := $(e2fsdroid_src)
 LOCAL_MODULE := e2fsdroid
+LOCAL_C_INCLUDES := $(LOCAL_PATH)/../../misc/
 LOCAL_SHARED_LIBRARIES := libext2fs-host \
     libext2_com_err-host \
     libcutils \
@@ -22,6 +26,7 @@ include $(BUILD_HOST_EXECUTABLE)
 include $(CLEAR_VARS)
 LOCAL_SRC_FILES := $(e2fsdroid_src)
 LOCAL_MODULE := e2fsdroid
+LOCAL_C_INCLUDES := $(LOCAL_PATH)/../../misc/
 LOCAL_SHARED_LIBRARIES := libext2fs \
     libext2_com_err \
     libcutils \
diff --git a/contrib/android/base_fs.c b/contrib/android/base_fs.c
index d2b44f91..2dcb5fe3 100644
--- a/contrib/android/base_fs.c
+++ b/contrib/android/base_fs.c
@@ -9,6 +9,121 @@ struct base_fs {
 	struct basefs_entry entry;
 };
 
+static FILE *basefs_open(const char *file)
+{
+	char *line = NULL;
+	size_t len;
+	FILE *f = fopen(file, "r");
+	if (!f)
+		return NULL;
+
+	if (getline(&line, &len, f) == -1 || !line)
+		goto err_getline;
+
+	if (strncmp(line, BASE_FS_VERSION, strlen(BASE_FS_VERSION)))
+		goto err_header;
+
+	free(line);
+	return f;
+
+err_header:
+	free(line);
+err_getline:
+	fclose(f);
+	return NULL;
+}
+
+static struct basefs_entry *basefs_readline(FILE *f, const char *mountpoint,
+					    int *err)
+{
+	char *line = NULL, *saveptr1, *saveptr2, *block_range, *block;
+	int offset;
+	size_t len;
+	struct basefs_entry *entry = NULL;
+	blk64_t range_start, range_end;
+
+	if (getline(&line, &len, f) == -1) {
+		if (feof(f))
+			goto end;
+		goto err_getline;
+	}
+
+	entry = calloc(1, sizeof(*entry));
+	if (!entry)
+		goto err_alloc;
+
+	/*
+	 * With BASEFS version 1.0, a typical line looks like this:
+	 * /bin/mke2fs 5000-5004,8000,9000-9990
+	 */
+	if (sscanf(line, "%ms%n", &entry->path, &offset) != 1)
+		goto err_sscanf;
+	len = strlen(mountpoint);
+	memmove(entry->path, entry->path + len, strlen(entry->path) - len + 1);
+
+	while (line[offset] == ' ')
+		++offset;
+
+	block_range = strtok_r(line + offset, ",\n", &saveptr1);
+	while (block_range) {
+		block = strtok_r(block_range, "-", &saveptr2);
+		if (!block)
+			break;
+		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);
+		block_range = strtok_r(NULL, ",\n", &saveptr1);
+	}
+end:
+	*err = 0;
+	free(line);
+	return entry;
+
+err_sscanf:
+	free(entry);
+err_alloc:
+	free(line);
+err_getline:
+	*err = 1;
+	return NULL;
+}
+
+static void free_base_fs_entry(void *e)
+{
+	struct basefs_entry *entry = e;
+	if (entry) {
+		free(entry->path);
+		free(entry);
+	}
+}
+
+struct hashmap *basefs_parse(const char *file, const char *mountpoint)
+{
+	int err;
+	struct hashmap *entries = NULL;
+	struct basefs_entry *entry;
+	FILE *f = basefs_open(file);
+	if (!f)
+		return NULL;
+	entries = hashmap_create(djb2_hash, free_base_fs_entry, 1024);
+	if (!entries)
+		goto end;
+
+	while ((entry = basefs_readline(f, mountpoint, &err)))
+		hashmap_add(entries, entry, entry->path);
+
+	if (err) {
+		fclose(f);
+		hashmap_free(entries);
+		return NULL;
+	}
+end:
+	fclose(f);
+	return entries;
+}
+
 static void *init(const char *file, const char *mountpoint)
 {
 	struct base_fs *params = malloc(sizeof(*params));
diff --git a/contrib/android/base_fs.h b/contrib/android/base_fs.h
index bd441078..94bae293 100644
--- a/contrib/android/base_fs.h
+++ b/contrib/android/base_fs.h
@@ -2,6 +2,7 @@
 # define BASE_FS_H
 
 # include "fsmap.h"
+# include "hashmap.h"
 # include "block_range.h"
 
 struct basefs_entry {
@@ -12,4 +13,6 @@ struct basefs_entry {
 
 extern struct fsmap_format base_fs_format;
 
+struct hashmap *basefs_parse(const char *file, const char *mountpoint);
+
 #endif /* !BASE_FS_H */
diff --git a/contrib/android/basefs_allocator.c b/contrib/android/basefs_allocator.c
new file mode 100644
index 00000000..3d014a22
--- /dev/null
+++ b/contrib/android/basefs_allocator.c
@@ -0,0 +1,147 @@
+#include <sys/types.h>
+#include <sys/stat.h>
+#include "basefs_allocator.h"
+#include "block_range.h"
+#include "hashmap.h"
+#include "base_fs.h"
+
+struct base_fs_allocator {
+	struct hashmap *entries;
+	struct basefs_entry *cur_entry;
+};
+
+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)
+{
+	while (blocks) {
+		ext2fs_unmark_block_bitmap_range2(fs->block_map, blocks->start,
+			blocks->end - blocks->start + 1);
+		blocks = blocks->next;
+	}
+}
+
+static void fs_reserve_blocks_range(ext2_filsys fs, struct block_range *blocks)
+{
+	while (blocks) {
+		ext2fs_mark_block_bitmap_range2(fs->block_map,
+			blocks->start, blocks->end - blocks->start + 1);
+		blocks = blocks->next;
+	}
+}
+
+errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file,
+			     const char *mountpoint)
+{
+	errcode_t retval;
+	struct basefs_entry *e;
+	struct hashmap_entry *it = NULL;
+	struct base_fs_allocator *allocator;
+	struct hashmap *entries = basefs_parse(file, mountpoint);
+	if (!entries)
+		return -1;
+
+	allocator = malloc(sizeof(*allocator));
+	if (!allocator)
+		goto err_alloc;
+
+	retval = ext2fs_read_bitmaps(fs);
+	if (retval)
+		goto err_bitmap;
+	while ((e = hashmap_iter_in_order(entries, &it)))
+		fs_reserve_blocks_range(fs, e->head);
+
+	allocator->cur_entry = NULL;
+	allocator->entries = entries;
+
+	/* Overhide the default allocator */
+	fs->get_alloc_block2 = basefs_block_allocator;
+	fs->priv_data = allocator;
+
+	return 0;
+
+err_bitmap:
+	free(allocator);
+err_alloc:
+	hashmap_free(entries);
+	return EXIT_FAILURE;
+}
+
+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;
+		}
+	} else { /* Allocate a new block */
+		retval = ext2fs_new_block2(fs, goal, fs->block_map, ret);
+		if (retval)
+			return retval;
+		ext2fs_mark_block_bitmap2(fs->block_map, *ret);
+	}
+	return 0;
+}
+
+void base_fs_alloc_cleanup(ext2_filsys fs)
+{
+	struct basefs_entry *e;
+	struct hashmap_entry *it = NULL;
+	struct base_fs_allocator *allocator = fs->priv_data;
+
+	while ((e = 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->priv_data = NULL;
+	fs->get_alloc_block2 = NULL;
+	hashmap_free(allocator->entries);
+	free(allocator);
+}
+
+errcode_t base_fs_alloc_set_target(ext2_filsys fs, const char *target_path,
+	const char *name EXT2FS_ATTR((unused)),
+	ext2_ino_t parent_ino EXT2FS_ATTR((unused)),
+	ext2_ino_t root EXT2FS_ATTR((unused)), mode_t mode)
+{
+	struct base_fs_allocator *allocator = fs->priv_data;
+
+	if (mode != S_IFREG)
+		return 0;
+
+	if (allocator)
+		allocator->cur_entry = hashmap_lookup(allocator->entries,
+						      target_path);
+	return 0;
+}
+
+errcode_t base_fs_alloc_unset_target(ext2_filsys fs,
+        const char *target_path EXT2FS_ATTR((unused)),
+	const char *name EXT2FS_ATTR((unused)),
+	ext2_ino_t parent_ino EXT2FS_ATTR((unused)),
+	ext2_ino_t root EXT2FS_ATTR((unused)), mode_t mode)
+{
+	struct base_fs_allocator *allocator = fs->priv_data;
+
+	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;
+	return 0;
+}
diff --git a/contrib/android/basefs_allocator.h b/contrib/android/basefs_allocator.h
new file mode 100644
index 00000000..f1109cd6
--- /dev/null
+++ b/contrib/android/basefs_allocator.h
@@ -0,0 +1,16 @@
+#ifndef BASE_FS_ALLOCATOR_H
+# define BASE_FS_ALLOCATOR_H
+
+# include <time.h>
+# include <ext2fs/ext2fs.h>
+
+errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file,
+			     const char *mountpoint);
+void base_fs_alloc_cleanup(ext2_filsys fs);
+
+errcode_t base_fs_alloc_set_target(ext2_filsys fs, const char *target_path,
+	const char *name, ext2_ino_t parent_ino, ext2_ino_t root, mode_t mode);
+errcode_t base_fs_alloc_unset_target(ext2_filsys fs, const char *target_path,
+	const char *name, ext2_ino_t parent_ino, ext2_ino_t root, mode_t mode);
+
+#endif /* !BASE_FS_ALLOCATOR_H */
diff --git a/contrib/android/e2fsdroid.c b/contrib/android/e2fsdroid.c
index 7237030a..e3b819fb 100644
--- a/contrib/android/e2fsdroid.c
+++ b/contrib/android/e2fsdroid.c
@@ -8,24 +8,28 @@
 #include "perms.h"
 #include "base_fs.h"
 #include "block_list.h"
+#include "basefs_allocator.h"
+#include "create_inode.h"
 
-const char *prog_name = "e2fsdroid";
-const char *in_file;
-const char *block_list;
-const char *basefs_out;
-const char *mountpoint = "";
+static char *prog_name = "e2fsdroid";
+static char *in_file;
+static char *block_list;
+static char *basefs_out;
+static char *basefs_in;
+static char *mountpoint = "";
 static time_t fixed_time;
 static char *fs_config_file;
 static char *file_contexts;
 static char *product_out;
+static char *src_dir;
 static int android_configure;
-int android_sparse_file = 1;
+static int android_sparse_file = 1;
 
 static void usage(int ret)
 {
 	fprintf(stderr, "%s [-B block_list] [-D basefs_out] [-T timestamp]\n"
 			"\t[-C fs_config] [-S file_contexts] [-p product_out]\n"
-			"\t[-a mountpoint] [-e] image\n",
+			"\t[-a mountpoint] [-d basefs_in] [-f src_dir] [-e] image\n",
                 prog_name);
 	exit(ret);
 }
@@ -53,10 +57,11 @@ int main(int argc, char *argv[])
 	errcode_t retval;
 	io_manager io_mgr;
 	ext2_filsys fs = NULL;
+        struct fs_ops_callbacks fs_callbacks = { NULL, NULL };
 
 	add_error_table(&et_ext2_error_table);
 
-	while ((c = getopt (argc, argv, "T:C:S:p:a:D:B:e")) != EOF) {
+	while ((c = getopt (argc, argv, "T:C:S:p:a:D:d:B:f:e")) != EOF) {
 		switch (c) {
 		case 'T':
 			fixed_time = strtoul(optarg, &p, 0);
@@ -79,9 +84,15 @@ int main(int argc, char *argv[])
 		case 'D':
 			basefs_out = absolute_path(optarg);
 			break;
+		case 'd':
+			basefs_in = absolute_path(optarg);
+			break;
 		case 'B':
 			block_list = absolute_path(optarg);
 			break;
+		case 'f':
+			src_dir = absolute_path(optarg);
+			break;
 		case 'e':
 			android_sparse_file = 0;
 			break;
@@ -102,6 +113,31 @@ int main(int argc, char *argv[])
 		return retval;
 	}
 
+	if (src_dir) {
+		ext2fs_read_bitmaps(fs);
+		if (basefs_in) {
+			retval = base_fs_alloc_load(fs, basefs_in, mountpoint);
+			if (retval) {
+				com_err(prog_name, retval, "%s",
+				"while reading base_fs file");
+			    exit(1);
+			}
+			fs_callbacks.create_new_inode =
+				base_fs_alloc_set_target;
+			fs_callbacks.end_create_new_inode =
+				base_fs_alloc_unset_target;
+		}
+		retval = populate_fs2(fs, EXT2_ROOT_INO, src_dir,
+				      EXT2_ROOT_INO, &fs_callbacks);
+		if (retval) {
+			com_err(prog_name, retval, "%s",
+			"while populating file system");
+		    exit(1);
+		}
+		if (basefs_in)
+			base_fs_alloc_cleanup(fs);
+	}
+
 	if (android_configure) {
 		retval = android_configure_fs(fs, product_out, mountpoint,
 			file_contexts, fs_config_file, fixed_time);
diff --git a/contrib/android/hashmap.c b/contrib/android/hashmap.c
new file mode 100644
index 00000000..eee00714
--- /dev/null
+++ b/contrib/android/hashmap.c
@@ -0,0 +1,76 @@
+#include "hashmap.h"
+#include <string.h>
+
+uint32_t djb2_hash(const void *str)
+{
+	int c;
+	const char *s = str;
+	uint32_t hash = 5381;
+
+	while ((c = *s++))
+		hash = ((hash << 5) + hash) + c;
+	return hash;
+}
+
+struct hashmap *hashmap_create(uint32_t(*hash_fct)(const void*),
+			       void(*free_fct)(void*), size_t size)
+{
+	struct hashmap *h = calloc(sizeof(struct hashmap) +
+				      sizeof(struct hashmap_entry) * size, 1);
+	h->size = size;
+	h->free = free_fct;
+	h->hash = hash_fct;
+	h->first = h->last = NULL;
+	return h;
+}
+
+void hashmap_add(struct hashmap *h, void *data, const void *key)
+{
+	uint32_t hash = h->hash(key) % h->size;
+	struct hashmap_entry *e = malloc(sizeof(*e));
+
+	e->data = data;
+	e->key = key;
+	e->next = h->entries[hash];
+	h->entries[hash] = e;
+
+	e->list_prev = NULL;
+	e->list_next = h->first;
+	if (h->first)
+		h->first->list_prev = e;
+	h->first = e;
+	if (!h->last)
+		h->last = e;
+}
+
+void *hashmap_lookup(struct hashmap *h, const void *key)
+{
+	struct hashmap_entry *iter;
+	uint32_t hash = h->hash(key) % h->size;
+
+	for (iter = h->entries[hash]; iter; iter = iter->next)
+		if (!strcmp(iter->key, key))
+			return iter->data;
+	return NULL;
+}
+
+void *hashmap_iter_in_order(struct hashmap *h, struct hashmap_entry **it)
+{
+	*it = *it ? (*it)->list_next : h->first;
+	return *it ? (*it)->data : NULL;
+}
+
+void hashmap_free(struct hashmap *h)
+{
+	for (size_t i = 0; i < h->size; ++i) {
+		struct hashmap_entry *it = h->entries[i];
+		while (it) {
+			struct hashmap_entry *tmp = it->next;
+			if (h->free)
+				h->free(it->data);
+			free(it);
+			it = tmp;
+		}
+	}
+	free(h);
+}
diff --git a/contrib/android/hashmap.h b/contrib/android/hashmap.h
new file mode 100644
index 00000000..70d0ed19
--- /dev/null
+++ b/contrib/android/hashmap.h
@@ -0,0 +1,32 @@
+#ifndef HASHMAP_H
+# define HASHMAP_H
+
+# include <stdlib.h>
+# include <stdint.h>
+
+struct hashmap {
+	uint32_t size;
+	uint32_t(*hash)(const void *key);
+	void(*free)(void*);
+	struct hashmap_entry *first;
+	struct hashmap_entry *last;
+	struct hashmap_entry {
+		void *data;
+		const void *key;
+		struct hashmap_entry *next;
+		struct hashmap_entry *list_next;
+		struct hashmap_entry *list_prev;
+	} *entries[0];
+};
+
+struct hashmap *hashmap_create(uint32_t(*hash_fct)(const void*),
+			       void(*free_fct)(void*), size_t size);
+void hashmap_add(struct hashmap *h, void *data, const void *key);
+void *hashmap_lookup(struct hashmap *h, const void *key);
+void *hashmap_iter_in_order(struct hashmap *h, struct hashmap_entry **it);
+void hashmap_del(struct hashmap *h, struct hashmap_entry *e);
+void hashmap_free(struct hashmap *h);
+
+uint32_t djb2_hash(const void *str);
+
+#endif /* !HASHMAP_H */