[thirdparty/e2fsprogs.git] / e2fsck / encrypted_files.c

/*
 * encrypted_files.c --- save information about encrypted files
 *
 * Copyright 2019 Google LLC
 *
 * %Begin-Header%
 * This file may be redistributed under the terms of the GNU Public
 * License.
 * %End-Header%
 */

/*
 * e2fsck pass 1 (inode table scan) creates a map from inode number to
 * encryption policy for all encrypted inodes.  But it's optimized so that the
 * full xattrs aren't saved but rather only 32-bit "policy IDs", since usually
 * many inodes share the same encryption policy.  This requires also maintaining
 * a second map, from policy to policy ID.  See add_encrypted_file().
 *
 * We also use run-length encoding to save memory when many adjacent inodes
 * share the same encryption policy, which is often the case too.
 *
 * e2fsck pass 2 (directory structure check) uses the inode => policy ID map to
 * verify that all regular files, directories, and symlinks in encrypted
 * directories use the directory's encryption policy.
 */

#include "config.h"

#include "e2fsck.h"
#include "problem.h"
#include "ext2fs/rbtree.h"

#define FSCRYPT_KEY_DESCRIPTOR_SIZE	8
#define FSCRYPT_KEY_IDENTIFIER_SIZE	16
#define FS_KEY_DERIVATION_NONCE_SIZE	16

struct fscrypt_context_v1 {
	__u8 version;
	__u8 contents_encryption_mode;
	__u8 filenames_encryption_mode;
	__u8 flags;
	__u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
	__u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE];
};

struct fscrypt_context_v2 {
	__u8 version;
	__u8 contents_encryption_mode;
	__u8 filenames_encryption_mode;
	__u8 flags;
	__u8 __reserved[4];
	__u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
	__u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE];
};

/* On-disk format of encryption xattr */
union fscrypt_context {
	__u8 version;
	struct fscrypt_context_v1 v1;
	struct fscrypt_context_v2 v2;
};

struct fscrypt_policy_v1 {
	__u8 version;
	__u8 contents_encryption_mode;
	__u8 filenames_encryption_mode;
	__u8 flags;
	__u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
};

struct fscrypt_policy_v2 {
	__u8 version;
	__u8 contents_encryption_mode;
	__u8 filenames_encryption_mode;
	__u8 flags;
	__u8 __reserved[4];
	__u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
};

/* The encryption "policy" is the fscrypt_context excluding the nonce. */
union fscrypt_policy {
	__u8 version;
	struct fscrypt_policy_v1 v1;
	struct fscrypt_policy_v2 v2;
};

/* A range of inodes which share the same encryption policy */
struct encrypted_file_range {
	ext2_ino_t		first_ino;
	ext2_ino_t		last_ino;
	__u32			policy_id;
};

/* Information about the encrypted files which have been seen so far */
struct encrypted_file_info {
	/*
	 * Map from inode number to encryption policy ID, implemented as a
	 * sorted array of inode ranges, each of which shares the same policy.
	 * Inodes are added in order of increasing inode number.
	 *
	 * Freed after pass 2.
	 */
	struct encrypted_file_range	*file_ranges;
	size_t				file_ranges_count;
	size_t				file_ranges_capacity;

	/*
	 * Map from encryption policy to encryption policy ID, for the unique
	 * encryption policies that have been seen so far.  next_policy_id is
	 * the next available ID, starting at 0.
	 *
	 * Freed after pass 1.
	 */
	struct rb_root		policies;
	__u32			next_policy_id;
};

/* Entry in encrypted_file_info::policies */
struct policy_map_entry {
	union fscrypt_policy	policy;
	__u32			policy_id;
	struct rb_node		node;
};

static int cmp_fscrypt_policies(e2fsck_t ctx, const union fscrypt_policy *a,
				const union fscrypt_policy *b)
{
	if (a->version != b->version)
		return (int)a->version - (int)b->version;

	switch (a->version) {
	case 1:
		return memcmp(a, b, sizeof(a->v1));
	case 2:
		return memcmp(a, b, sizeof(a->v2));
	}
	fatal_error(ctx, "Unhandled encryption policy version");
	return 0;
}

/* Read an inode's encryption xattr. */
static errcode_t read_encryption_xattr(e2fsck_t ctx, ext2_ino_t ino,
				       void **value, size_t *value_len)
{
	struct ext2_xattr_handle *h;
	errcode_t retval;

	retval = ext2fs_xattrs_open(ctx->fs, ino, &h);
	if (retval)
		return retval;

	retval = ext2fs_xattrs_read(h);
	if (retval == 0)
		retval = ext2fs_xattr_get(h, "c", value, value_len);

	ext2fs_xattrs_close(&h);
	return retval;
}

/*
 * Convert an fscrypt_context to an fscrypt_policy.  Returns 0,
 * CORRUPT_ENCRYPTION_POLICY, or UNRECOGNIZED_ENCRYPTION_POLICY.
 */
static __u32 fscrypt_context_to_policy(const void *xattr, size_t xattr_size,
				       union fscrypt_policy *policy_u)
{
	const union fscrypt_context *ctx_u = xattr;

	if (xattr_size < 1)
		return CORRUPT_ENCRYPTION_POLICY;
	switch (ctx_u->version) {
	case 0:
		return CORRUPT_ENCRYPTION_POLICY;
	case 1: {
		struct fscrypt_policy_v1 *policy = &policy_u->v1;
		const struct fscrypt_context_v1 *ctx = &ctx_u->v1;

		if (xattr_size != sizeof(*ctx))
			return CORRUPT_ENCRYPTION_POLICY;
		policy->version = ctx->version;
		policy->contents_encryption_mode =
			ctx->contents_encryption_mode;
		policy->filenames_encryption_mode =
			ctx->filenames_encryption_mode;
		policy->flags = ctx->flags;
		memcpy(policy->master_key_descriptor,
		       ctx->master_key_descriptor,
		       sizeof(policy->master_key_descriptor));
		return 0;
	}
	case 2: {
		struct fscrypt_policy_v2 *policy = &policy_u->v2;
		const struct fscrypt_context_v2 *ctx = &ctx_u->v2;

		if (xattr_size != sizeof(*ctx))
			return CORRUPT_ENCRYPTION_POLICY;
		policy->version = ctx->version;
		policy->contents_encryption_mode =
			ctx->contents_encryption_mode;
		policy->filenames_encryption_mode =
			ctx->filenames_encryption_mode;
		policy->flags = ctx->flags;
		memcpy(policy->__reserved, ctx->__reserved,
		       sizeof(policy->__reserved));
		memcpy(policy->master_key_identifier,
		       ctx->master_key_identifier,
		       sizeof(policy->master_key_identifier));
		return 0;
	}
	}
	return UNRECOGNIZED_ENCRYPTION_POLICY;
}

/*
 * Read an inode's encryption xattr and get/allocate its encryption policy ID,
 * or alternatively use one of the special IDs NO_ENCRYPTION_POLICY,
 * CORRUPT_ENCRYPTION_POLICY, or UNRECOGNIZED_ENCRYPTION_POLICY.
 *
 * Returns nonzero only if out of memory.
 */
static errcode_t get_encryption_policy_id(e2fsck_t ctx, ext2_ino_t ino,
					  __u32 *policy_id_ret)
{
	struct encrypted_file_info *info = ctx->encrypted_files;
	struct rb_node **new = &info->policies.rb_node;
	struct rb_node *parent = NULL;
	void *xattr;
	size_t xattr_size;
	union fscrypt_policy policy;
	__u32 policy_id;
	struct policy_map_entry *entry;
	errcode_t retval;

	retval = read_encryption_xattr(ctx, ino, &xattr, &xattr_size);
	if (retval == EXT2_ET_NO_MEMORY)
		return retval;
	if (retval) {
		*policy_id_ret = NO_ENCRYPTION_POLICY;
		return 0;
	}

	/* Translate the xattr to an fscrypt_policy, if possible. */
	policy_id = fscrypt_context_to_policy(xattr, xattr_size, &policy);
	ext2fs_free_mem(&xattr);
	if (policy_id != 0)
		goto out;

	/* Check if the policy was already seen. */
	while (*new) {
		int res;

		parent = *new;
		entry = ext2fs_rb_entry(parent, struct policy_map_entry, node);
		res = cmp_fscrypt_policies(ctx, &policy, &entry->policy);
		if (res < 0) {
			new = &parent->rb_left;
		} else if (res > 0) {
			new = &parent->rb_right;
		} else {
			/* Policy already seen.  Use existing ID. */
			policy_id = entry->policy_id;
			goto out;
		}
	}

	/* First time seeing this policy.  Allocate a new policy ID. */
	retval = ext2fs_get_mem(sizeof(*entry), &entry);
	if (retval)
		goto out;
	policy_id = info->next_policy_id++;
	entry->policy_id = policy_id;
	entry->policy = policy;
	ext2fs_rb_link_node(&entry->node, parent, new);
	ext2fs_rb_insert_color(&entry->node, &info->policies);
out:
	*policy_id_ret = policy_id;
	return retval;
}

static int handle_nomem(e2fsck_t ctx, struct problem_context *pctx,
			size_t size_needed)
{
	pctx->num = size_needed;
	fix_problem(ctx, PR_1_ALLOCATE_ENCRYPTED_INODE_LIST, pctx);
	/* Should never get here */
	ctx->flags |= E2F_FLAG_ABORT;
	return 0;
}

static int append_ino_and_policy_id(e2fsck_t ctx, struct problem_context *pctx,
				    ext2_ino_t ino, __u32 policy_id)
{
	struct encrypted_file_info *info = ctx->encrypted_files;
	struct encrypted_file_range *range;

	/* See if we can just extend the last range. */
	if (info->file_ranges_count > 0) {
		range = &info->file_ranges[info->file_ranges_count - 1];

		if (ino <= range->last_ino) {
			/* Should never get here */
			fatal_error(ctx,
				    "Encrypted inodes processed out of order");
		}

		if (ino == range->last_ino + 1 &&
		    policy_id == range->policy_id) {
			range->last_ino++;
			return 0;
		}
	}
	/* Nope, a new range is needed. */

	if (info->file_ranges_count == info->file_ranges_capacity) {
		/* Double the capacity by default. */
		size_t new_capacity = info->file_ranges_capacity * 2;

		/* ... but go from 0 to 128 right away. */
		if (new_capacity < 128)
			new_capacity = 128;

		/* We won't need more than the filesystem's inode count. */
		if (new_capacity > ctx->fs->super->s_inodes_count)
			new_capacity = ctx->fs->super->s_inodes_count;

		/* To be safe, ensure the capacity really increases. */
		if (new_capacity < info->file_ranges_capacity + 1)
			new_capacity = info->file_ranges_capacity + 1;

		if (ext2fs_resize_mem(info->file_ranges_capacity *
					sizeof(*range),
				      new_capacity * sizeof(*range),
				      &info->file_ranges) != 0)
			return handle_nomem(ctx, pctx,
					    new_capacity * sizeof(*range));

		info->file_ranges_capacity = new_capacity;
	}
	range = &info->file_ranges[info->file_ranges_count++];
	range->first_ino = ino;
	range->last_ino = ino;
	range->policy_id = policy_id;
	return 0;
}

/*
 * Handle an inode that has EXT4_ENCRYPT_FL set during pass 1.  Normally this
 * just finds the unique ID that identifies the inode's encryption policy
 * (allocating a new ID if needed), and adds the inode number and its policy ID
 * to the encrypted_file_info so that it's available in pass 2.
 *
 * But this also handles:
 * - If the inode doesn't have an encryption xattr at all, offer to clear the
 *   encrypt flag.
 * - If the encryption xattr is clearly corrupt, tell the caller that the whole
 *   inode should be cleared.
 * - To be future-proof: if the encryption xattr has an unrecognized version
 *   number, it *might* be valid, so we don't consider it invalid.  But we can't
 *   do much with it, so give all such policies the same ID,
 *   UNRECOGNIZED_ENCRYPTION_POLICY.
 *
 * Returns -1 if the inode should be cleared, otherwise 0.
 */
int add_encrypted_file(e2fsck_t ctx, struct problem_context *pctx)
{
	struct encrypted_file_info *info = ctx->encrypted_files;
	ext2_ino_t ino = pctx->ino;
	__u32 policy_id;

	/* Allocate the encrypted_file_info if needed. */
	if (info == NULL) {
		if (ext2fs_get_memzero(sizeof(*info), &info) != 0)
			return handle_nomem(ctx, pctx, sizeof(*info));
		ctx->encrypted_files = info;
	}

	/* Get a unique ID for this inode's encryption policy. */
	if (get_encryption_policy_id(ctx, ino, &policy_id) != 0)
		return handle_nomem(ctx, pctx, 0 /* unknown size */);
	if (policy_id == NO_ENCRYPTION_POLICY) {
		if (fix_problem(ctx, PR_1_MISSING_ENCRYPTION_XATTR, pctx)) {
			pctx->inode->i_flags &= ~EXT4_ENCRYPT_FL;
			e2fsck_write_inode(ctx, ino, pctx->inode, "pass1");
		}
		return 0;
	} else if (policy_id == CORRUPT_ENCRYPTION_POLICY) {
		if (fix_problem(ctx, PR_1_CORRUPT_ENCRYPTION_XATTR, pctx))
			return -1;
		return 0;
	}

	/* Store this ino => policy_id mapping in the encrypted_file_info. */
	return append_ino_and_policy_id(ctx, pctx, ino, policy_id);
}

/*
 * Find the ID of an inode's encryption policy, using the information saved
 * earlier.
 *
 * If the inode is encrypted, returns the policy ID or
 * UNRECOGNIZED_ENCRYPTION_POLICY.  Else, returns NO_ENCRYPTION_POLICY.
 */
__u32 find_encryption_policy(e2fsck_t ctx, ext2_ino_t ino)
{
	const struct encrypted_file_info *info = ctx->encrypted_files;
	size_t l, r;

	if (info == NULL)
		return NO_ENCRYPTION_POLICY;
	l = 0;
	r = info->file_ranges_count;
	while (l < r) {
		size_t m = l + (r - l) / 2;
		const struct encrypted_file_range *range =
			&info->file_ranges[m];

		if (ino < range->first_ino)
			r = m;
		else if (ino > range->last_ino)
			l = m + 1;
		else
			return range->policy_id;
	}
	return NO_ENCRYPTION_POLICY;
}

/* Destroy ctx->encrypted_files->policies */
void destroy_encryption_policy_map(e2fsck_t ctx)
{
	struct encrypted_file_info *info = ctx->encrypted_files;

	if (info) {
		struct rb_root *policies = &info->policies;

		while (!ext2fs_rb_empty_root(policies)) {
			struct policy_map_entry *entry;

			entry = ext2fs_rb_entry(policies->rb_node,
						struct policy_map_entry, node);
			ext2fs_rb_erase(&entry->node, policies);
			ext2fs_free_mem(&entry);
		}
		info->next_policy_id = 0;
	}
}

/* Destroy ctx->encrypted_files */
void destroy_encrypted_file_info(e2fsck_t ctx)
{
	struct encrypted_file_info *info = ctx->encrypted_files;

	if (info) {
		destroy_encryption_policy_map(ctx);
		ext2fs_free_mem(&info->file_ranges);
		ext2fs_free_mem(&info);
		ctx->encrypted_files = NULL;
	}
}
Commit	Line	Data
2ba05753 EB	1	/*
	2	* encrypted_files.c --- save information about encrypted files
	3	*
	4	* Copyright 2019 Google LLC
	5	*
	6	* %Begin-Header%
	7	* This file may be redistributed under the terms of the GNU Public
	8	* License.
	9	* %End-Header%
	10	*/
	11
	12	/*
	13	* e2fsck pass 1 (inode table scan) creates a map from inode number to
	14	* encryption policy for all encrypted inodes. But it's optimized so that the
	15	* full xattrs aren't saved but rather only 32-bit "policy IDs", since usually
	16	* many inodes share the same encryption policy. This requires also maintaining
	17	* a second map, from policy to policy ID. See add_encrypted_file().
	18	*
	19	* We also use run-length encoding to save memory when many adjacent inodes
	20	* share the same encryption policy, which is often the case too.
	21	*
	22	* e2fsck pass 2 (directory structure check) uses the inode => policy ID map to
	23	* verify that all regular files, directories, and symlinks in encrypted
	24	* directories use the directory's encryption policy.
	25	*/
	26
	27	#include "config.h"
	28
	29	#include "e2fsck.h"
	30	#include "problem.h"
	31	#include "ext2fs/rbtree.h"
	32
	33	#define FSCRYPT_KEY_DESCRIPTOR_SIZE 8
	34	#define FSCRYPT_KEY_IDENTIFIER_SIZE 16
	35	#define FS_KEY_DERIVATION_NONCE_SIZE 16
	36
	37	struct fscrypt_context_v1 {
	38	__u8 version;
	39	__u8 contents_encryption_mode;
	40	__u8 filenames_encryption_mode;
	41	__u8 flags;
	42	__u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
	43	__u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE];
	44	};
	45
	46	struct fscrypt_context_v2 {
	47	__u8 version;
	48	__u8 contents_encryption_mode;
	49	__u8 filenames_encryption_mode;
	50	__u8 flags;
	51	__u8 __reserved[4];
	52	__u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
	53	__u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE];
	54	};
	55
	56	/* On-disk format of encryption xattr */
	57	union fscrypt_context {
	58	__u8 version;
	59	struct fscrypt_context_v1 v1;
	60	struct fscrypt_context_v2 v2;
	61	};
	62
	63	struct fscrypt_policy_v1 {
	64	__u8 version;
65	__u8 contents_encryption_mode;
66	__u8 filenames_encryption_mode;
67	__u8 flags;
68	__u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
69	};
70
71	struct fscrypt_policy_v2 {
72	__u8 version;
73	__u8 contents_encryption_mode;
74	__u8 filenames_encryption_mode;
75	__u8 flags;
76	__u8 __reserved[4];
77	__u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
78	};
79
80	/* The encryption "policy" is the fscrypt_context excluding the nonce. */
81	union fscrypt_policy {
82	__u8 version;
83	struct fscrypt_policy_v1 v1;
84	struct fscrypt_policy_v2 v2;
85	};
86
87	/* A range of inodes which share the same encryption policy */
88	struct encrypted_file_range {
89	ext2_ino_t first_ino;
90	ext2_ino_t last_ino;
91	__u32 policy_id;
92	};
93
94	/* Information about the encrypted files which have been seen so far */
95	struct encrypted_file_info {
96	/*
97	* Map from inode number to encryption policy ID, implemented as a
98	* sorted array of inode ranges, each of which shares the same policy.
99	* Inodes are added in order of increasing inode number.
100	*
101	* Freed after pass 2.
102	*/
103	struct encrypted_file_range *file_ranges;
104	size_t file_ranges_count;
105	size_t file_ranges_capacity;
106
107	/*
108	* Map from encryption policy to encryption policy ID, for the unique
109	* encryption policies that have been seen so far. next_policy_id is
110	* the next available ID, starting at 0.
111	*
112	* Freed after pass 1.
113	*/
114	struct rb_root policies;
115	__u32 next_policy_id;
116	};
117
118	/* Entry in encrypted_file_info::policies */
119	struct policy_map_entry {
120	union fscrypt_policy policy;
121	__u32 policy_id;
122	struct rb_node node;
123	};
124
125	static int cmp_fscrypt_policies(e2fsck_t ctx, const union fscrypt_policy *a,
126	const union fscrypt_policy *b)
127	{
128	if (a->version != b->version)
129	return (int)a->version - (int)b->version;
130
131	switch (a->version) {
132	case 1:
133	return memcmp(a, b, sizeof(a->v1));
134	case 2:
135	return memcmp(a, b, sizeof(a->v2));
136	}
137	fatal_error(ctx, "Unhandled encryption policy version");
138	return 0;
139	}
140
141	/* Read an inode's encryption xattr. */
142	static errcode_t read_encryption_xattr(e2fsck_t ctx, ext2_ino_t ino,
143	void *value, size_t value_len)
144	{
145	struct ext2_xattr_handle *h;
146	errcode_t retval;
147
148	retval = ext2fs_xattrs_open(ctx->fs, ino, &h);
149	if (retval)
150	return retval;
151
152	retval = ext2fs_xattrs_read(h);
153	if (retval == 0)
154	retval = ext2fs_xattr_get(h, "c", value, value_len);
155
156	ext2fs_xattrs_close(&h);
157	return retval;
158	}
159
160	/*
161	* Convert an fscrypt_context to an fscrypt_policy. Returns 0,
162	* CORRUPT_ENCRYPTION_POLICY, or UNRECOGNIZED_ENCRYPTION_POLICY.
163	*/
164	static __u32 fscrypt_context_to_policy(const void *xattr, size_t xattr_size,
165	union fscrypt_policy *policy_u)
166	{
167	const union fscrypt_context *ctx_u = xattr;
168
169	if (xattr_size < 1)
170	return CORRUPT_ENCRYPTION_POLICY;
171	switch (ctx_u->version) {
172	case 0:
173	return CORRUPT_ENCRYPTION_POLICY;
174	case 1: {
175	struct fscrypt_policy_v1 *policy = &policy_u->v1;
176	const struct fscrypt_context_v1 *ctx = &ctx_u->v1;
177
178	if (xattr_size != sizeof(*ctx))
179	return CORRUPT_ENCRYPTION_POLICY;
180	policy->version = ctx->version;
181	policy->contents_encryption_mode =
182	ctx->contents_encryption_mode;
183	policy->filenames_encryption_mode =
184	ctx->filenames_encryption_mode;
185	policy->flags = ctx->flags;
186	memcpy(policy->master_key_descriptor,
187	ctx->master_key_descriptor,
188	sizeof(policy->master_key_descriptor));
189	return 0;
190	}
191	case 2: {
192	struct fscrypt_policy_v2 *policy = &policy_u->v2;
193	const struct fscrypt_context_v2 *ctx = &ctx_u->v2;
194
195	if (xattr_size != sizeof(*ctx))
196	return CORRUPT_ENCRYPTION_POLICY;
197	policy->version = ctx->version;
198	policy->contents_encryption_mode =
199	ctx->contents_encryption_mode;
200	policy->filenames_encryption_mode =
201	ctx->filenames_encryption_mode;
202	policy->flags = ctx->flags;
203	memcpy(policy->__reserved, ctx->__reserved,
204	sizeof(policy->__reserved));
205	memcpy(policy->master_key_identifier,
206	ctx->master_key_identifier,
207	sizeof(policy->master_key_identifier));
208	return 0;
209	}
210	}
211	return UNRECOGNIZED_ENCRYPTION_POLICY;
212	}
213
214	/*
215	* Read an inode's encryption xattr and get/allocate its encryption policy ID,
216	* or alternatively use one of the special IDs NO_ENCRYPTION_POLICY,
217	* CORRUPT_ENCRYPTION_POLICY, or UNRECOGNIZED_ENCRYPTION_POLICY.
218	*
219	* Returns nonzero only if out of memory.
220	*/
221	static errcode_t get_encryption_policy_id(e2fsck_t ctx, ext2_ino_t ino,
222	__u32 *policy_id_ret)
223	{
224	struct encrypted_file_info *info = ctx->encrypted_files;
225	struct rb_node **new = &info->policies.rb_node;
226	struct rb_node *parent = NULL;
227	void *xattr;
228	size_t xattr_size;
229	union fscrypt_policy policy;
230	__u32 policy_id;
231	struct policy_map_entry *entry;
232	errcode_t retval;
233
234	retval = read_encryption_xattr(ctx, ino, &xattr, &xattr_size);
235	if (retval == EXT2_ET_NO_MEMORY)
236	return retval;
237	if (retval) {
238	*policy_id_ret = NO_ENCRYPTION_POLICY;
239	return 0;
240	}
241
242	/* Translate the xattr to an fscrypt_policy, if possible. */
243	policy_id = fscrypt_context_to_policy(xattr, xattr_size, &policy);
244	ext2fs_free_mem(&xattr);
245	if (policy_id != 0)
246	goto out;
247
248	/* Check if the policy was already seen. */
249	while (*new) {
250	int res;
251
252	parent = *new;
253	entry = ext2fs_rb_entry(parent, struct policy_map_entry, node);
254	res = cmp_fscrypt_policies(ctx, &policy, &entry->policy);
255	if (res < 0) {
256	new = &parent->rb_left;
257	} else if (res > 0) {
258	new = &parent->rb_right;
259	} else {
260	/* Policy already seen. Use existing ID. */
261	policy_id = entry->policy_id;
262	goto out;
263	}
264	}
265
266	/* First time seeing this policy. Allocate a new policy ID. */
267	retval = ext2fs_get_mem(sizeof(*entry), &entry);
268	if (retval)
269	goto out;
270	policy_id = info->next_policy_id++;
271	entry->policy_id = policy_id;
272	entry->policy = policy;
273	ext2fs_rb_link_node(&entry->node, parent, new);
274	ext2fs_rb_insert_color(&entry->node, &info->policies);
275	out:
276	*policy_id_ret = policy_id;
277	return retval;
278	}
279
280	static int handle_nomem(e2fsck_t ctx, struct problem_context *pctx,
281	size_t size_needed)
282	{
283	pctx->num = size_needed;
284	fix_problem(ctx, PR_1_ALLOCATE_ENCRYPTED_INODE_LIST, pctx);
285	/* Should never get here */
286	ctx->flags \|= E2F_FLAG_ABORT;
287	return 0;
288	}
289
290	static int append_ino_and_policy_id(e2fsck_t ctx, struct problem_context *pctx,
291	ext2_ino_t ino, __u32 policy_id)
292	{
293	struct encrypted_file_info *info = ctx->encrypted_files;
294	struct encrypted_file_range *range;
295
296	/* See if we can just extend the last range. */
297	if (info->file_ranges_count > 0) {
298	range = &info->file_ranges[info->file_ranges_count - 1];
299
300	if (ino <= range->last_ino) {
301	/* Should never get here */
302	fatal_error(ctx,
303	"Encrypted inodes processed out of order");
304	}
305
306	if (ino == range->last_ino + 1 &&
307	policy_id == range->policy_id) {
308	range->last_ino++;
309	return 0;
310	}
311	}
312	/* Nope, a new range is needed. */
313
314	if (info->file_ranges_count == info->file_ranges_capacity) {
315	/* Double the capacity by default. */
316	size_t new_capacity = info->file_ranges_capacity * 2;
317
318	/* ... but go from 0 to 128 right away. */
319	if (new_capacity < 128)
320	new_capacity = 128;
321
322	/* We won't need more than the filesystem's inode count. */
323	if (new_capacity > ctx->fs->super->s_inodes_count)
324	new_capacity = ctx->fs->super->s_inodes_count;
325
326	/* To be safe, ensure the capacity really increases. */
327	if (new_capacity < info->file_ranges_capacity + 1)
328	new_capacity = info->file_ranges_capacity + 1;
329
330	if (ext2fs_resize_mem(info->file_ranges_capacity *
331	sizeof(*range),
332	new_capacity * sizeof(*range),
333	&info->file_ranges) != 0)
334	return handle_nomem(ctx, pctx,
335	new_capacity * sizeof(*range));
336
337	info->file_ranges_capacity = new_capacity;
338	}
339	range = &info->file_ranges[info->file_ranges_count++];
340	range->first_ino = ino;
341	range->last_ino = ino;
342	range->policy_id = policy_id;
343	return 0;
344	}
345
346	/*
347	* Handle an inode that has EXT4_ENCRYPT_FL set during pass 1. Normally this
348	* just finds the unique ID that identifies the inode's encryption policy
349	* (allocating a new ID if needed), and adds the inode number and its policy ID
350	* to the encrypted_file_info so that it's available in pass 2.
351	*
352	* But this also handles:
353	* - If the inode doesn't have an encryption xattr at all, offer to clear the
354	* encrypt flag.
355	* - If the encryption xattr is clearly corrupt, tell the caller that the whole
356	* inode should be cleared.
357	* - To be future-proof: if the encryption xattr has an unrecognized version
358	* number, it might be valid, so we don't consider it invalid. But we can't
359	* do much with it, so give all such policies the same ID,
360	* UNRECOGNIZED_ENCRYPTION_POLICY.
361	*
362	* Returns -1 if the inode should be cleared, otherwise 0.
363	*/
364	int add_encrypted_file(e2fsck_t ctx, struct problem_context *pctx)
365	{
366	struct encrypted_file_info *info = ctx->encrypted_files;
367	ext2_ino_t ino = pctx->ino;
368	__u32 policy_id;
369
370	/* Allocate the encrypted_file_info if needed. */
371	if (info == NULL) {
372	if (ext2fs_get_memzero(sizeof(*info), &info) != 0)
373	return handle_nomem(ctx, pctx, sizeof(*info));
374	ctx->encrypted_files = info;
375	}
376
377	/* Get a unique ID for this inode's encryption policy. */
378	if (get_encryption_policy_id(ctx, ino, &policy_id) != 0)
379	return handle_nomem(ctx, pctx, 0 /* unknown size */);
380	if (policy_id == NO_ENCRYPTION_POLICY) {
381	if (fix_problem(ctx, PR_1_MISSING_ENCRYPTION_XATTR, pctx)) {
382	pctx->inode->i_flags &= ~EXT4_ENCRYPT_FL;
383	e2fsck_write_inode(ctx, ino, pctx->inode, "pass1");
384	}
385	return 0;
386	} else if (policy_id == CORRUPT_ENCRYPTION_POLICY) {
387	if (fix_problem(ctx, PR_1_CORRUPT_ENCRYPTION_XATTR, pctx))
388	return -1;
389	return 0;
390	}
391
392	/* Store this ino => policy_id mapping in the encrypted_file_info. */
393	return append_ino_and_policy_id(ctx, pctx, ino, policy_id);
394	}
395
396	/*
397	* Find the ID of an inode's encryption policy, using the information saved
398	* earlier.
399	*
400	* If the inode is encrypted, returns the policy ID or
401	* UNRECOGNIZED_ENCRYPTION_POLICY. Else, returns NO_ENCRYPTION_POLICY.
402	*/
403	__u32 find_encryption_policy(e2fsck_t ctx, ext2_ino_t ino)
404	{
405	const struct encrypted_file_info *info = ctx->encrypted_files;
406	size_t l, r;
407
408	if (info == NULL)
409	return NO_ENCRYPTION_POLICY;
410	l = 0;
411	r = info->file_ranges_count;
412	while (l < r) {
413	size_t m = l + (r - l) / 2;
414	const struct encrypted_file_range *range =
415	&info->file_ranges[m];
416
417	if (ino < range->first_ino)
418	r = m;
419	else if (ino > range->last_ino)
420	l = m + 1;
421	else
422	return range->policy_id;
423	}
424	return NO_ENCRYPTION_POLICY;
425	}
426
427	/* Destroy ctx->encrypted_files->policies */
428	void destroy_encryption_policy_map(e2fsck_t ctx)
429	{
430	struct encrypted_file_info *info = ctx->encrypted_files;
431
432	if (info) {
433	struct rb_root *policies = &info->policies;
434
435	while (!ext2fs_rb_empty_root(policies)) {
436	struct policy_map_entry *entry;
437
438	entry = ext2fs_rb_entry(policies->rb_node,
439	struct policy_map_entry, node);
440	ext2fs_rb_erase(&entry->node, policies);
441	ext2fs_free_mem(&entry);
442	}
443	info->next_policy_id = 0;
444	}
445	}
446
447	/* Destroy ctx->encrypted_files */
448	void destroy_encrypted_file_info(e2fsck_t ctx)
449	{
450	struct encrypted_file_info *info = ctx->encrypted_files;
451
452	if (info) {
453	destroy_encryption_policy_map(ctx);
454	ext2fs_free_mem(&info->file_ranges);
455	ext2fs_free_mem(&info);
456	ctx->encrypted_files = NULL;
457	}
458	}