2 * encrypted_files.c --- save information about encrypted files
4 * Copyright 2019 Google LLC
7 * This file may be redistributed under the terms of the GNU Public
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().
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.
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.
31 #include "ext2fs/rbtree.h"
33 #define FSCRYPT_KEY_DESCRIPTOR_SIZE 8
34 #define FSCRYPT_KEY_IDENTIFIER_SIZE 16
35 #define FS_KEY_DERIVATION_NONCE_SIZE 16
37 struct fscrypt_context_v1 {
39 __u8 contents_encryption_mode;
40 __u8 filenames_encryption_mode;
42 __u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
43 __u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE];
46 struct fscrypt_context_v2 {
48 __u8 contents_encryption_mode;
49 __u8 filenames_encryption_mode;
52 __u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
53 __u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE];
56 /* On-disk format of encryption xattr */
57 union fscrypt_context {
59 struct fscrypt_context_v1 v1;
60 struct fscrypt_context_v2 v2;
63 struct fscrypt_policy_v1 {
65 __u8 contents_encryption_mode;
66 __u8 filenames_encryption_mode;
68 __u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
71 struct fscrypt_policy_v2 {
73 __u8 contents_encryption_mode;
74 __u8 filenames_encryption_mode;
77 __u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
80 /* The encryption "policy" is the fscrypt_context excluding the nonce. */
81 union fscrypt_policy {
83 struct fscrypt_policy_v1 v1;
84 struct fscrypt_policy_v2 v2;
87 /* A range of inodes which share the same encryption policy */
88 struct encrypted_file_range {
94 /* Information about the encrypted files which have been seen so far */
95 struct encrypted_file_info {
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.
101 * Freed after pass 2.
103 struct encrypted_file_range *file_ranges;
104 size_t file_ranges_count;
105 size_t file_ranges_capacity;
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.
112 * Freed after pass 1.
114 struct rb_root policies;
115 __u32 next_policy_id;
118 /* Entry in encrypted_file_info::policies */
119 struct policy_map_entry {
120 union fscrypt_policy policy;
125 static int cmp_fscrypt_policies(e2fsck_t ctx, const union fscrypt_policy *a,
126 const union fscrypt_policy *b)
128 if (a->version != b->version)
129 return (int)a->version - (int)b->version;
131 switch (a->version) {
133 return memcmp(a, b, sizeof(a->v1));
135 return memcmp(a, b, sizeof(a->v2));
137 fatal_error(ctx, "Unhandled encryption policy version");
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)
145 struct ext2_xattr_handle *h;
148 retval = ext2fs_xattrs_open(ctx->fs, ino, &h);
152 retval = ext2fs_xattrs_read(h);
154 retval = ext2fs_xattr_get(h, "c", value, value_len);
156 ext2fs_xattrs_close(&h);
161 * Convert an fscrypt_context to an fscrypt_policy. Returns 0,
162 * CORRUPT_ENCRYPTION_POLICY, or UNRECOGNIZED_ENCRYPTION_POLICY.
164 static __u32 fscrypt_context_to_policy(const void *xattr, size_t xattr_size,
165 union fscrypt_policy *policy_u)
167 const union fscrypt_context *ctx_u = xattr;
170 return CORRUPT_ENCRYPTION_POLICY;
171 switch (ctx_u->version) {
173 return CORRUPT_ENCRYPTION_POLICY;
175 struct fscrypt_policy_v1 *policy = &policy_u->v1;
176 const struct fscrypt_context_v1 *ctx = &ctx_u->v1;
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));
192 struct fscrypt_policy_v2 *policy = &policy_u->v2;
193 const struct fscrypt_context_v2 *ctx = &ctx_u->v2;
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));
211 return UNRECOGNIZED_ENCRYPTION_POLICY;
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.
219 * Returns nonzero only if out of memory.
221 static errcode_t get_encryption_policy_id(e2fsck_t ctx, ext2_ino_t ino,
222 __u32 *policy_id_ret)
224 struct encrypted_file_info *info = ctx->encrypted_files;
225 struct rb_node **new = &info->policies.rb_node;
226 struct rb_node *parent = NULL;
229 union fscrypt_policy policy;
231 struct policy_map_entry *entry;
234 retval = read_encryption_xattr(ctx, ino, &xattr, &xattr_size);
235 if (retval == EXT2_ET_NO_MEMORY)
238 *policy_id_ret = NO_ENCRYPTION_POLICY;
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);
248 /* Check if the policy was already seen. */
253 entry = ext2fs_rb_entry(parent, struct policy_map_entry, node);
254 res = cmp_fscrypt_policies(ctx, &policy, &entry->policy);
256 new = &parent->rb_left;
257 } else if (res > 0) {
258 new = &parent->rb_right;
260 /* Policy already seen. Use existing ID. */
261 policy_id = entry->policy_id;
266 /* First time seeing this policy. Allocate a new policy ID. */
267 retval = ext2fs_get_mem(sizeof(*entry), &entry);
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);
276 *policy_id_ret = policy_id;
280 static int handle_nomem(e2fsck_t ctx, struct problem_context *pctx,
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;
290 static int append_ino_and_policy_id(e2fsck_t ctx, struct problem_context *pctx,
291 ext2_ino_t ino, __u32 policy_id)
293 struct encrypted_file_info *info = ctx->encrypted_files;
294 struct encrypted_file_range *range;
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];
300 if (ino <= range->last_ino) {
301 /* Should never get here */
303 "Encrypted inodes processed out of order");
306 if (ino == range->last_ino + 1 &&
307 policy_id == range->policy_id) {
312 /* Nope, a new range is needed. */
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;
318 /* ... but go from 0 to 128 right away. */
319 if (new_capacity < 128)
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;
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;
330 if (ext2fs_resize_mem(info->file_ranges_capacity *
332 new_capacity * sizeof(*range),
333 &info->file_ranges) != 0)
334 return handle_nomem(ctx, pctx,
335 new_capacity * sizeof(*range));
337 info->file_ranges_capacity = new_capacity;
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;
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.
352 * But this also handles:
353 * - If the inode doesn't have an encryption xattr at all, offer to clear the
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.
362 * Returns -1 if the inode should be cleared, otherwise 0.
364 int add_encrypted_file(e2fsck_t ctx, struct problem_context *pctx)
366 struct encrypted_file_info *info = ctx->encrypted_files;
367 ext2_ino_t ino = pctx->ino;
370 /* Allocate the encrypted_file_info if needed. */
372 if (ext2fs_get_memzero(sizeof(*info), &info) != 0)
373 return handle_nomem(ctx, pctx, sizeof(*info));
374 ctx->encrypted_files = info;
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");
386 } else if (policy_id == CORRUPT_ENCRYPTION_POLICY) {
387 if (fix_problem(ctx, PR_1_CORRUPT_ENCRYPTION_XATTR, pctx))
392 /* Store this ino => policy_id mapping in the encrypted_file_info. */
393 return append_ino_and_policy_id(ctx, pctx, ino, policy_id);
397 * Find the ID of an inode's encryption policy, using the information saved
400 * If the inode is encrypted, returns the policy ID or
401 * UNRECOGNIZED_ENCRYPTION_POLICY. Else, returns NO_ENCRYPTION_POLICY.
403 __u32 find_encryption_policy(e2fsck_t ctx, ext2_ino_t ino)
405 const struct encrypted_file_info *info = ctx->encrypted_files;
409 return NO_ENCRYPTION_POLICY;
411 r = info->file_ranges_count;
413 size_t m = l + (r - l) / 2;
414 const struct encrypted_file_range *range =
415 &info->file_ranges[m];
417 if (ino < range->first_ino)
419 else if (ino > range->last_ino)
422 return range->policy_id;
424 return NO_ENCRYPTION_POLICY;
427 /* Destroy ctx->encrypted_files->policies */
428 void destroy_encryption_policy_map(e2fsck_t ctx)
430 struct encrypted_file_info *info = ctx->encrypted_files;
433 struct rb_root *policies = &info->policies;
435 while (!ext2fs_rb_empty_root(policies)) {
436 struct policy_map_entry *entry;
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);
443 info->next_policy_id = 0;
447 /* Destroy ctx->encrypted_files */
448 void destroy_encrypted_file_info(e2fsck_t ctx)
450 struct encrypted_file_info *info = ctx->encrypted_files;
453 destroy_encryption_policy_map(ctx);
454 ext2fs_free_mem(&info->file_ranges);
455 ext2fs_free_mem(&info);
456 ctx->encrypted_files = NULL;