ANDROID: Incremental fs: Build merkle tree when enabling verity

For incfs files that were created without a merkle tree, enabling verity
requires building a merkle tree first. Although this is the same logic
as verity performs, it is not that easy to reconcile the two given that
incfs has the merkle tree potentially when verity is not enabled.

Bug: 160634504
Test: incfs_test passes
Signed-off-by: Paul Lawrence <paullawrence@google.com>

Change-Id: Ia15a4051fa3362820846d65859e3af76b77f8cc4

6 files changed, 345 insertions, 20 deletions

diff --git a/fs/incfs/data_mgmt.c b/fs/incfs/data_mgmt.c
index fb4d42287c23..6640b9346bb9 100644
--- a/fs/incfs/data_mgmt.c
+++ b/fs/incfs/data_mgmt.c
@@ -601,7 +601,11 @@ static int validate_hash_tree(struct backing_file_context *bfc, struct file *f,
 	int hash_per_block;
 	pgoff_t file_pages;
 
-	tree = df->df_hash_tree;
+	/*
+	 * Memory barrier to make sure tree is fully present if added via enable
+	 * verity
+	 */
+	tree = smp_load_acquire(&df->df_hash_tree);
 	sig = df->df_signature;
 	if (!tree || !sig)
 		return 0;
@@ -1509,6 +1513,7 @@ static int incfs_scan_metadata_chain(struct data_file *df)
 	int records_count = 0;
 	int error = 0;
 	struct backing_file_context *bfc = NULL;
+	int nondata_block_count;
 
 	if (!df || !df->df_backing_file_context)
 		return -EFAULT;
@@ -1543,15 +1548,25 @@ static int incfs_scan_metadata_chain(struct data_file *df)
 	} else
 		result = records_count;
 
+	nondata_block_count = df->df_total_block_count -
+		df->df_data_block_count;
 	if (df->df_hash_tree) {
 		int hash_block_count = get_blocks_count_for_size(
 			df->df_hash_tree->hash_tree_area_size);
 
-		if (df->df_data_block_count + hash_block_count !=
-		    df->df_total_block_count)
+		/*
+		 * Files that were created with a hash tree have the hash tree
+		 * included in the block map, i.e. nondata_block_count ==
+		 * hash_block_count.  Files whose hash tree was added by
+		 * FS_IOC_ENABLE_VERITY will still have the original block
+		 * count, i.e. nondata_block_count == 0.
+		 */
+		if (nondata_block_count != hash_block_count &&
+		    nondata_block_count != 0)
 			result = -EINVAL;
-	} else if (df->df_data_block_count != df->df_total_block_count)
+	} else if (nondata_block_count != 0) {
 		result = -EINVAL;
+	}
 
 	kfree(handler);
 	return result;
diff --git a/fs/incfs/format.c b/fs/incfs/format.c
index fc4ad25c5de7..5e87bb8dbab0 100644
--- a/fs/incfs/format.c
+++ b/fs/incfs/format.c
@@ -246,7 +246,8 @@ int incfs_write_blockmap_to_backing_file(struct backing_file_context *bfc,
 }
 
 int incfs_write_signature_to_backing_file(struct backing_file_context *bfc,
-					  struct mem_range sig, u32 tree_size)
+					struct mem_range sig, u32 tree_size,
+					loff_t *tree_offset, loff_t *sig_offset)
 {
 	struct incfs_file_signature sg = {};
 	int result = 0;
@@ -265,12 +266,10 @@ int incfs_write_signature_to_backing_file(struct backing_file_context *bfc,
 	sg.sg_header.h_record_size = cpu_to_le16(sizeof(sg));
 	sg.sg_header.h_next_md_offset = cpu_to_le64(0);
 	if (sig.data != NULL && sig.len > 0) {
-		loff_t pos = incfs_get_end_offset(bfc->bc_file);
-
 		sg.sg_sig_size = cpu_to_le32(sig.len);
-		sg.sg_sig_offset = cpu_to_le64(pos);
+		sg.sg_sig_offset = cpu_to_le64(rollback_pos);
 
-		result = write_to_bf(bfc, sig.data, sig.len, pos);
+		result = write_to_bf(bfc, sig.data, sig.len, rollback_pos);
 		if (result)
 			goto err;
 	}
@@ -306,6 +305,13 @@ err:
 	if (result)
 		/* Error, rollback file changes */
 		truncate_backing_file(bfc, rollback_pos);
+	else {
+		if (tree_offset)
+			*tree_offset = tree_area_pos;
+		if (sig_offset)
+			*sig_offset = rollback_pos;
+	}
+
 	return result;
 }
 
diff --git a/fs/incfs/format.h b/fs/incfs/format.h
index 69c6d90e33c4..14e475b79a16 100644
--- a/fs/incfs/format.h
+++ b/fs/incfs/format.h
@@ -236,6 +236,10 @@ struct incfs_blockmap {
  * definition of incfs_new_file_args::signature_info for an explanation of this
  * blob. Specifically, it contains the root hash, but it does *not* contain
  * anything that the kernel treats as a signature.
+ *
+ * When FS_IOC_ENABLE_VERITY is called on a file without this record, an APK V4
+ * signature blob and a hash tree are added to the file, and then this metadata
+ * record is created to record their locations.
  */
 struct incfs_file_signature {
 	struct incfs_md_header sg_header;
@@ -367,7 +371,8 @@ int incfs_write_hash_block_to_backing_file(struct backing_file_context *bfc,
 					   loff_t file_size);
 
 int incfs_write_signature_to_backing_file(struct backing_file_context *bfc,
-					  struct mem_range sig, u32 tree_size);
+				struct mem_range sig, u32 tree_size,
+				loff_t *tree_offset, loff_t *sig_offset);
 
 int incfs_write_status_to_backing_file(struct backing_file_context *bfc,
 				       loff_t status_offset,
diff --git a/fs/incfs/pseudo_files.c b/fs/incfs/pseudo_files.c
index 954c0384e156..e6fdc9d18111 100644
--- a/fs/incfs/pseudo_files.c
+++ b/fs/incfs/pseudo_files.c
@@ -354,8 +354,9 @@ static int init_new_file(struct mount_info *mi, struct dentry *dentry,
 			goto out;
 		}
 
-		error = incfs_write_signature_to_backing_file(
-			bfc, raw_signature, hash_tree->hash_tree_area_size);
+		error = incfs_write_signature_to_backing_file(bfc,
+				raw_signature, hash_tree->hash_tree_area_size,
+				NULL, NULL);
 		if (error)
 			goto out;
 
diff --git a/fs/incfs/verity.c b/fs/incfs/verity.c
index 372bad7d8085..8a94c14b38af 100644
--- a/fs/incfs/verity.c
+++ b/fs/incfs/verity.c
@@ -278,6 +278,227 @@ out:
 	return verity_file_digest;
 }
 
+static int incfs_build_merkle_tree(struct file *f, struct data_file *df,
+			     struct backing_file_context *bfc,
+			     struct mtree *hash_tree, loff_t hash_offset,
+			     struct incfs_hash_alg *alg, struct mem_range hash)
+{
+	int error = 0;
+	int limit, lvl, i, result;
+	struct mem_range buf = {.len = INCFS_DATA_FILE_BLOCK_SIZE};
+	struct mem_range tmp = {.len = 2 * INCFS_DATA_FILE_BLOCK_SIZE};
+
+	buf.data = (u8 *)__get_free_pages(GFP_NOFS, get_order(buf.len));
+	tmp.data = (u8 *)__get_free_pages(GFP_NOFS, get_order(tmp.len));
+	if (!buf.data || !tmp.data) {
+		error = -ENOMEM;
+		goto out;
+	}
+
+	/*
+	 * lvl - 1 is the level we are reading, lvl the level we are writing
+	 * lvl == -1 means actual blocks
+	 * lvl == hash_tree->depth means root hash
+	 */
+	limit = df->df_data_block_count;
+	for (lvl = 0; lvl <= hash_tree->depth; lvl++) {
+		for (i = 0; i < limit; ++i) {
+			loff_t hash_level_offset;
+			struct mem_range partial_buf = buf;
+
+			if (lvl == 0)
+				result = incfs_read_data_file_block(partial_buf,
+							f, i, 0, 0, 0, tmp);
+			else {
+				hash_level_offset = hash_offset +
+				       hash_tree->hash_level_suboffset[lvl - 1];
+
+				result = incfs_kread(bfc, partial_buf.data,
+						partial_buf.len,
+						hash_level_offset + i *
+						INCFS_DATA_FILE_BLOCK_SIZE);
+			}
+
+			if (result < 0) {
+				error = result;
+				goto out;
+			}
+
+			partial_buf.len = result;
+			error = incfs_calc_digest(alg, partial_buf, hash);
+			if (error)
+				goto out;
+
+			/*
+			 * last level - only one hash to take and it is stored
+			 * in the incfs signature record
+			 */
+			if (lvl == hash_tree->depth)
+				break;
+
+			hash_level_offset = hash_offset +
+				hash_tree->hash_level_suboffset[lvl];
+
+			result = incfs_kwrite(bfc, hash.data, hash.len,
+					hash_level_offset + hash.len * i);
+
+			if (result < 0) {
+				error = result;
+				goto out;
+			}
+
+			if (result != hash.len) {
+				error = -EIO;
+				goto out;
+			}
+		}
+		limit = DIV_ROUND_UP(limit,
+				     INCFS_DATA_FILE_BLOCK_SIZE / hash.len);
+	}
+
+out:
+	free_pages((unsigned long)tmp.data, get_order(tmp.len));
+	free_pages((unsigned long)buf.data, get_order(buf.len));
+	return error;
+}
+
+/*
+ * incfs files have a signature record that is separate from the
+ * verity_signature record. The signature record does not actually contain a
+ * signature, rather it contains the size/offset of the hash tree, and a binary
+ * blob which contains the root hash and potentially a signature.
+ *
+ * If the file was created with a signature record, then this function simply
+ * returns.
+ *
+ * Otherwise it will create a signature record with a minimal binary blob as
+ * defined by the structure below, create space for the hash tree and then
+ * populate it using incfs_build_merkle_tree
+ */
+static int incfs_add_signature_record(struct file *f)
+{
+	/* See incfs_parse_signature */
+	struct {
+		__le32 version;
+		__le32 size_of_hash_info_section;
+		struct {
+			__le32 hash_algorithm;
+			u8 log2_blocksize;
+			__le32 salt_size;
+			u8 salt[0];
+			__le32 hash_size;
+			u8 root_hash[32];
+		} __packed hash_section;
+		__le32 size_of_signing_info_section;
+		u8 signing_info_section[0];
+	} __packed sig = {
+		.version = cpu_to_le32(INCFS_SIGNATURE_VERSION),
+		.size_of_hash_info_section =
+			cpu_to_le32(sizeof(sig.hash_section)),
+		.hash_section = {
+			.hash_algorithm = cpu_to_le32(INCFS_HASH_TREE_SHA256),
+			.log2_blocksize = ilog2(INCFS_DATA_FILE_BLOCK_SIZE),
+			.hash_size = cpu_to_le32(SHA256_DIGEST_SIZE),
+		},
+	};
+
+	struct data_file *df = get_incfs_data_file(f);
+	struct mtree *hash_tree = NULL;
+	struct backing_file_context *bfc;
+	int error;
+	loff_t hash_offset, sig_offset;
+	struct incfs_hash_alg *alg = incfs_get_hash_alg(INCFS_HASH_TREE_SHA256);
+	u8 hash_buf[INCFS_MAX_HASH_SIZE];
+	int hash_size = alg->digest_size;
+	struct mem_range hash = range(hash_buf, hash_size);
+	int result;
+	struct incfs_df_signature *signature = NULL;
+
+	if (!df)
+		return -EINVAL;
+
+	if (df->df_header_flags & INCFS_FILE_MAPPED)
+		return -EINVAL;
+
+	/* Already signed? */
+	if (df->df_signature && df->df_hash_tree)
+		return 0;
+
+	if (df->df_signature || df->df_hash_tree)
+		return -EFSCORRUPTED;
+
+	/* Add signature metadata record to file */
+	hash_tree = incfs_alloc_mtree(range((u8 *)&sig, sizeof(sig)),
+				      df->df_data_block_count);
+	if (IS_ERR(hash_tree))
+		return PTR_ERR(hash_tree);
+
+	bfc = df->df_backing_file_context;
+	if (!bfc) {
+		error = -EFSCORRUPTED;
+		goto out;
+	}
+
+	error = mutex_lock_interruptible(&bfc->bc_mutex);
+	if (error)
+		goto out;
+
+	error = incfs_write_signature_to_backing_file(bfc,
+				range((u8 *)&sig, sizeof(sig)),
+				hash_tree->hash_tree_area_size,
+				&hash_offset, &sig_offset);
+	mutex_unlock(&bfc->bc_mutex);
+	if (error)
+		goto out;
+
+	/* Populate merkle tree */
+	error = incfs_build_merkle_tree(f, df, bfc, hash_tree, hash_offset, alg,
+				  hash);
+	if (error)
+		goto out;
+
+	/* Update signature metadata record */
+	memcpy(sig.hash_section.root_hash, hash.data, alg->digest_size);
+	result = incfs_kwrite(bfc, &sig, sizeof(sig), sig_offset);
+	if (result < 0) {
+		error = result;
+		goto out;
+	}
+
+	if (result != sizeof(sig)) {
+		error = -EIO;
+		goto out;
+	}
+
+	/* Update in-memory records */
+	memcpy(hash_tree->root_hash, hash.data, alg->digest_size);
+	signature = kzalloc(sizeof(*signature), GFP_NOFS);
+	if (!signature) {
+		error = -ENOMEM;
+		goto out;
+	}
+	*signature = (struct incfs_df_signature) {
+		.hash_offset = hash_offset,
+		.hash_size = hash_tree->hash_tree_area_size,
+		.sig_offset = sig_offset,
+		.sig_size = sizeof(sig),
+	};
+	df->df_signature = signature;
+	signature = NULL;
+
+	/*
+	 * Use memory barrier to prevent readpage seeing the hash tree until
+	 * it's fully there
+	 */
+	smp_store_release(&df->df_hash_tree, hash_tree);
+	hash_tree = NULL;
+
+out:
+	kfree(signature);
+	kfree(hash_tree);
+	return error;
+}
+
 static int incfs_enable_verity(struct file *filp,
 			 const struct fsverity_enable_arg *arg)
 {
@@ -299,6 +520,10 @@ static int incfs_enable_verity(struct file *filp,
 		goto out;
 	}
 
+	err = incfs_add_signature_record(filp);
+	if (err)
+		goto out;
+
 	/* Get the signature if the user provided one */
 	if (arg->sig_size) {
 		signature = memdup_user(u64_to_user_ptr(arg->sig_ptr),
diff --git a/tools/testing/selftests/filesystems/incfs/incfs_test.c b/tools/testing/selftests/filesystems/incfs/incfs_test.c
index 0a86d9a5ba87..54e3284150ab 100644
--- a/tools/testing/selftests/filesystems/incfs/incfs_test.c
+++ b/tools/testing/selftests/filesystems/incfs/incfs_test.c
@@ -3777,7 +3777,7 @@ static int enable_verity(const char *mount_dir, struct test_file *file,
 		.sig_ptr = 0,
 	};
 	unsigned char *sig = NULL;
-	size_t sig_len;
+	size_t sig_len = 0;
 	struct {
 		__u8 version;           /* must be 1 */
 		__u8 hash_algorithm;    /* Merkle tree hash algorithm */
@@ -3813,13 +3813,15 @@ static int enable_verity(const char *mount_dir, struct test_file *file,
 	TESTEQUAL(flags & FS_VERITY_FL, 0);
 
 	/* First try to enable verity with random digest */
-	TESTEQUAL(sign(key, cert, (void *)&fsverity_signed_digest,
-		       sizeof(fsverity_signed_digest), &sig, &sig_len),
-		  0);
+	if (key) {
+		TESTEQUAL(sign(key, cert, (void *)&fsverity_signed_digest,
+			    sizeof(fsverity_signed_digest), &sig, &sig_len),
+			  0);
 
-	fear.sig_size = sig_len;
-	fear.sig_ptr = ptr_to_u64(sig);
-	TESTEQUAL(ioctl(fd, FS_IOC_ENABLE_VERITY, &fear), -1);
+		fear.sig_size = sig_len;
+		fear.sig_ptr = ptr_to_u64(sig);
+		TESTEQUAL(ioctl(fd, FS_IOC_ENABLE_VERITY, &fear), -1);
+	}
 
 	/* Now try with correct digest */
 	memcpy(fsverity_descriptor.root_hash, file->root_hash, 32);
@@ -3832,7 +3834,8 @@ static int enable_verity(const char *mount_dir, struct test_file *file,
 		goto out;
 	}
 
-	TESTEQUAL(sign(key, cert, (void *)&fsverity_signed_digest,
+	if (key)
+		TESTEQUAL(sign(key, cert, (void *)&fsverity_signed_digest,
 		       sizeof(fsverity_signed_digest), &sig, &sig_len),
 		  0);
 
@@ -3973,6 +3976,75 @@ out:
 	return result;
 }
 
+static int verity_file_valid(const char *mount_dir, struct test_file *file)
+{
+	int result = TEST_FAILURE;
+	char *filename = NULL;
+	int fd = -1;
+	uint8_t buffer[INCFS_DATA_FILE_BLOCK_SIZE];
+	struct incfs_get_file_sig_args gfsa = {
+		.file_signature = ptr_to_u64(buffer),
+		.file_signature_buf_size = sizeof(buffer),
+	};
+	int i;
+
+	TEST(filename = concat_file_name(mount_dir, file->name), filename);
+	TEST(fd = open(filename, O_RDONLY | O_CLOEXEC), fd != -1);
+	TESTEQUAL(ioctl(fd, INCFS_IOC_READ_FILE_SIGNATURE, &gfsa), 0);
+	for (i = 0; i < file->size; i += sizeof(buffer))
+		TESTEQUAL(pread(fd, buffer, sizeof(buffer), i),
+			  file->size - i > sizeof(buffer) ?
+				sizeof(buffer) : file->size - i);
+
+	result = TEST_SUCCESS;
+out:
+	close(fd);
+	free(filename);
+	return result;
+}
+
+static int enable_verity_test(const char *mount_dir)
+{
+	int result = TEST_FAILURE;
+	char *backing_dir = NULL;
+	bool installed;
+	int cmd_fd = -1;
+	struct test_files_set test = get_test_files_set();
+	int i;
+
+	TEST(backing_dir = create_backing_dir(mount_dir), backing_dir);
+	TESTEQUAL(mount_fs(mount_dir, backing_dir, 0), 0);
+	TEST(cmd_fd = open_commands_file(mount_dir), cmd_fd != -1);
+	TESTEQUAL(verity_installed(mount_dir, cmd_fd, &installed), 0);
+	if (!installed) {
+		result = TEST_SUCCESS;
+		goto out;
+	}
+	for (i = 0; i < test.files_count; ++i) {
+		struct test_file *file = &test.files[i];
+
+		TESTEQUAL(emit_file(cmd_fd, NULL, file->name, &file->id,
+				     file->size, NULL), 0);
+		TESTEQUAL(emit_test_file_data(mount_dir, file), 0);
+		TESTEQUAL(enable_verity(mount_dir, file, NULL, NULL, true), 0);
+	}
+
+	/* Check files are valid on disk */
+	close(cmd_fd);
+	cmd_fd = -1;
+	TESTEQUAL(umount(mount_dir), 0);
+	TESTEQUAL(mount_fs(mount_dir, backing_dir, 0), 0);
+	for (i = 0; i < test.files_count; ++i)
+		TESTEQUAL(verity_file_valid(mount_dir, &test.files[i]), 0);
+
+	result = TEST_SUCCESS;
+out:
+	close(cmd_fd);
+	umount(mount_dir);
+	free(backing_dir);
+	return result;
+}
+
 static char *setup_mount_dir()
 {
 	struct stat st;
@@ -4088,6 +4160,7 @@ int main(int argc, char *argv[])
 		MAKE_TEST(per_uid_read_timeouts_test),
 		MAKE_TEST(inotify_test),
 		MAKE_TEST(verity_test),
+		MAKE_TEST(enable_verity_test),
 	};
 #undef MAKE_TEST