1 // SPDX-License-Identifier: BSD-2-Clause
2 /*
3  * Copyright (c) 2017, Linaro Limited
4  */
5 
6 #include <assert.h>
7 #include <crypto/crypto.h>
8 #include <initcall.h>
9 #include <kernel/tee_common_otp.h>
10 #include <stdlib.h>
11 #include <string_ext.h>
12 #include <string.h>
13 #include <tee/fs_htree.h>
14 #include <tee/tee_fs_key_manager.h>
15 #include <tee/tee_fs_rpc.h>
16 #include <utee_defines.h>
17 #include <util.h>
18 
19 #define TEE_FS_HTREE_CHIP_ID_SIZE	32
20 #define TEE_FS_HTREE_HASH_ALG		TEE_ALG_SHA256
21 #define TEE_FS_HTREE_TSK_SIZE		TEE_FS_HTREE_HASH_SIZE
22 #define TEE_FS_HTREE_ENC_ALG		TEE_ALG_AES_ECB_NOPAD
23 #define TEE_FS_HTREE_ENC_SIZE		TEE_AES_BLOCK_SIZE
24 #define TEE_FS_HTREE_SSK_SIZE		TEE_FS_HTREE_HASH_SIZE
25 
26 #define TEE_FS_HTREE_AUTH_ENC_ALG	TEE_ALG_AES_GCM
27 #define TEE_FS_HTREE_HMAC_ALG		TEE_ALG_HMAC_SHA256
28 
29 #define BLOCK_NUM_TO_NODE_ID(num)	((num) + 1)
30 
31 #define NODE_ID_TO_BLOCK_NUM(id)	((id) - 1)
32 
33 /*
34  * The hash tree is implemented as a binary tree with the purpose to ensure
35  * integrity of the data in the nodes. The data in the nodes their turn
36  * provides both integrity and confidentiality of the data blocks.
37  *
38  * The hash tree is saved in a file as:
39  * +----------------------------+
40  * | htree_image.0		|
41  * | htree_image.1		|
42  * +----------------------------+
43  * | htree_node_image.1.0	|
44  * | htree_node_image.1.1	|
45  * +----------------------------+
46  * | htree_node_image.2.0	|
47  * | htree_node_image.2.1	|
48  * +----------------------------+
49  * | htree_node_image.3.0	|
50  * | htree_node_image.3.1	|
51  * +----------------------------+
52  * | htree_node_image.4.0	|
53  * | htree_node_image.4.1	|
54  * +----------------------------+
55  * ...
56  *
57  * htree_image is the header of the file, there's two instances of it. One
58  * which is committed and the other is used when updating the file. Which
59  * is committed is indicated by the "counter" field, the one with the
60  * largest value is selected.
61  *
62  * htree_node_image is a node in the hash tree, each node has two instances
63  * which is committed is decided by the parent node .flag bit
64  * HTREE_NODE_COMMITTED_CHILD. Which version is the committed version of
65  * node 1 is determined by the by the lowest bit of the counter field in
66  * the header.
67  *
68  * Note that nodes start counting at 1 while blocks at 0, this means that
69  * block 0 is represented by node 1.
70  *
71  * Where different elements are stored in the file is managed by the file
72  * system.
73  */
74 
75 #define HTREE_NODE_COMMITTED_BLOCK	BIT32(0)
76 /* n is 0 or 1 */
77 #define HTREE_NODE_COMMITTED_CHILD(n)	BIT32(1 + (n))
78 
79 struct htree_node {
80 	size_t id;
81 	bool dirty;
82 	bool block_updated;
83 	struct tee_fs_htree_node_image node;
84 	struct htree_node *parent;
85 	struct htree_node *child[2];
86 };
87 
88 struct tee_fs_htree {
89 	struct htree_node root;
90 	struct tee_fs_htree_image head;
91 	uint8_t fek[TEE_FS_HTREE_FEK_SIZE];
92 	struct tee_fs_htree_imeta imeta;
93 	bool dirty;
94 	const TEE_UUID *uuid;
95 	const struct tee_fs_htree_storage *stor;
96 	void *stor_aux;
97 };
98 
99 struct traverse_arg;
100 typedef TEE_Result (*traverse_cb_t)(struct traverse_arg *targ,
101 				    struct htree_node *node);
102 struct traverse_arg {
103 	struct tee_fs_htree *ht;
104 	traverse_cb_t cb;
105 	void *arg;
106 };
107 
rpc_read(struct tee_fs_htree * ht,enum tee_fs_htree_type type,size_t idx,size_t vers,void * data,size_t dlen)108 static TEE_Result rpc_read(struct tee_fs_htree *ht, enum tee_fs_htree_type type,
109 			   size_t idx, size_t vers, void *data, size_t dlen)
110 {
111 	TEE_Result res;
112 	struct tee_fs_rpc_operation op;
113 	size_t bytes;
114 	void *p;
115 
116 	res = ht->stor->rpc_read_init(ht->stor_aux, &op, type, idx, vers, &p);
117 	if (res != TEE_SUCCESS)
118 		return res;
119 
120 	res = ht->stor->rpc_read_final(&op, &bytes);
121 	if (res != TEE_SUCCESS)
122 		return res;
123 
124 	if (bytes != dlen)
125 		return TEE_ERROR_CORRUPT_OBJECT;
126 
127 	memcpy(data, p, dlen);
128 	return TEE_SUCCESS;
129 }
130 
rpc_read_head(struct tee_fs_htree * ht,size_t vers,struct tee_fs_htree_image * head)131 static TEE_Result rpc_read_head(struct tee_fs_htree *ht, size_t vers,
132 				struct tee_fs_htree_image *head)
133 {
134 	return rpc_read(ht, TEE_FS_HTREE_TYPE_HEAD, 0, vers,
135 			head, sizeof(*head));
136 }
137 
rpc_read_node(struct tee_fs_htree * ht,size_t node_id,size_t vers,struct tee_fs_htree_node_image * node)138 static TEE_Result rpc_read_node(struct tee_fs_htree *ht, size_t node_id,
139 				size_t vers,
140 				struct tee_fs_htree_node_image *node)
141 {
142 	return rpc_read(ht, TEE_FS_HTREE_TYPE_NODE, node_id - 1, vers,
143 			node, sizeof(*node));
144 }
145 
rpc_write(struct tee_fs_htree * ht,enum tee_fs_htree_type type,size_t idx,size_t vers,const void * data,size_t dlen)146 static TEE_Result rpc_write(struct tee_fs_htree *ht,
147 			    enum tee_fs_htree_type type, size_t idx,
148 			    size_t vers, const void *data, size_t dlen)
149 {
150 	TEE_Result res;
151 	struct tee_fs_rpc_operation op;
152 	void *p;
153 
154 	res = ht->stor->rpc_write_init(ht->stor_aux, &op, type, idx, vers, &p);
155 	if (res != TEE_SUCCESS)
156 		return res;
157 
158 	memcpy(p, data, dlen);
159 	return ht->stor->rpc_write_final(&op);
160 }
161 
rpc_write_head(struct tee_fs_htree * ht,size_t vers,const struct tee_fs_htree_image * head)162 static TEE_Result rpc_write_head(struct tee_fs_htree *ht, size_t vers,
163 				 const struct tee_fs_htree_image *head)
164 {
165 	return rpc_write(ht, TEE_FS_HTREE_TYPE_HEAD, 0, vers,
166 			 head, sizeof(*head));
167 }
168 
rpc_write_node(struct tee_fs_htree * ht,size_t node_id,size_t vers,const struct tee_fs_htree_node_image * node)169 static TEE_Result rpc_write_node(struct tee_fs_htree *ht, size_t node_id,
170 				 size_t vers,
171 				 const struct tee_fs_htree_node_image *node)
172 {
173 	return rpc_write(ht, TEE_FS_HTREE_TYPE_NODE, node_id - 1, vers,
174 			 node, sizeof(*node));
175 }
176 
traverse_post_order(struct traverse_arg * targ,struct htree_node * node)177 static TEE_Result traverse_post_order(struct traverse_arg *targ,
178 				      struct htree_node *node)
179 {
180 	TEE_Result res;
181 
182 	/*
183 	 * This function is recursing but not very deep, only with Log(N)
184 	 * maximum depth.
185 	 */
186 
187 	if (!node)
188 		return TEE_SUCCESS;
189 
190 	res = traverse_post_order(targ, node->child[0]);
191 	if (res != TEE_SUCCESS)
192 		return res;
193 
194 	res = traverse_post_order(targ, node->child[1]);
195 	if (res != TEE_SUCCESS)
196 		return res;
197 
198 	return targ->cb(targ, node);
199 }
200 
htree_traverse_post_order(struct tee_fs_htree * ht,traverse_cb_t cb,void * arg)201 static TEE_Result htree_traverse_post_order(struct tee_fs_htree *ht,
202 					    traverse_cb_t cb, void *arg)
203 {
204 	struct traverse_arg targ = { ht, cb, arg };
205 
206 	return traverse_post_order(&targ, &ht->root);
207 }
208 
node_id_to_level(size_t node_id)209 static size_t node_id_to_level(size_t node_id)
210 {
211 	assert(node_id && node_id < UINT_MAX);
212 	/* Calculate level of the node, root node (1) has level 1 */
213 	return sizeof(unsigned int) * 8 - __builtin_clz(node_id);
214 }
215 
find_closest_node(struct tee_fs_htree * ht,size_t node_id)216 static struct htree_node *find_closest_node(struct tee_fs_htree *ht,
217 					    size_t node_id)
218 {
219 	struct htree_node *node = &ht->root;
220 	size_t level = node_id_to_level(node_id);
221 	size_t n;
222 
223 	/* n = 1 because root node is level 1 */
224 	for (n = 1; n < level; n++) {
225 		struct htree_node *child;
226 		size_t bit_idx;
227 
228 		/*
229 		 * The difference between levels of the current node and
230 		 * the node we're looking for tells which bit decides
231 		 * direction in the tree.
232 		 *
233 		 * As the first bit has index 0 we'll subtract 1
234 		 */
235 		bit_idx = level - n - 1;
236 		child = node->child[((node_id >> bit_idx) & 1)];
237 		if (!child)
238 			return node;
239 		node = child;
240 	}
241 
242 	return node;
243 }
244 
find_node(struct tee_fs_htree * ht,size_t node_id)245 static struct htree_node *find_node(struct tee_fs_htree *ht, size_t node_id)
246 {
247 	struct htree_node *node = find_closest_node(ht, node_id);
248 
249 	if (node && node->id == node_id)
250 		return node;
251 	return NULL;
252 }
253 
get_node(struct tee_fs_htree * ht,bool create,size_t node_id,struct htree_node ** node_ret)254 static TEE_Result get_node(struct tee_fs_htree *ht, bool create,
255 			   size_t node_id, struct htree_node **node_ret)
256 {
257 	struct htree_node *node;
258 	struct htree_node *nc;
259 	size_t n;
260 
261 	node = find_closest_node(ht, node_id);
262 	if (!node)
263 		return TEE_ERROR_GENERIC;
264 	if (node->id == node_id)
265 		goto ret_node;
266 
267 	/*
268 	 * Trying to read beyond end of file should be caught earlier than
269 	 * here.
270 	 */
271 	if (!create)
272 		return TEE_ERROR_GENERIC;
273 
274 	/*
275 	 * Add missing nodes, some nodes may already be there. When we've
276 	 * processed the range all nodes up to node_id will be in the tree.
277 	 */
278 	for (n = node->id + 1; n <= node_id; n++) {
279 		node = find_closest_node(ht, n);
280 		if (node->id == n)
281 			continue;
282 		/* Node id n should be a child of node */
283 		assert((n >> 1) == node->id);
284 		assert(!node->child[n & 1]);
285 
286 		nc = calloc(1, sizeof(*nc));
287 		if (!nc)
288 			return TEE_ERROR_OUT_OF_MEMORY;
289 		nc->id = n;
290 		nc->parent = node;
291 		node->child[n & 1] = nc;
292 		node = nc;
293 	}
294 
295 	if (node->id > ht->imeta.max_node_id)
296 		ht->imeta.max_node_id = node->id;
297 
298 ret_node:
299 	*node_ret = node;
300 	return TEE_SUCCESS;
301 }
302 
get_idx_from_counter(uint32_t counter0,uint32_t counter1)303 static int get_idx_from_counter(uint32_t counter0, uint32_t counter1)
304 {
305 	if (!(counter0 & 1)) {
306 		if (!(counter1 & 1))
307 			return 0;
308 		if (counter0 > counter1)
309 			return 0;
310 		else
311 			return 1;
312 	}
313 
314 	if (counter1 & 1)
315 		return 1;
316 	else
317 		return -1;
318 }
319 
init_head_from_data(struct tee_fs_htree * ht,const uint8_t * hash)320 static TEE_Result init_head_from_data(struct tee_fs_htree *ht,
321 				      const uint8_t *hash)
322 {
323 	TEE_Result res;
324 	int idx;
325 
326 	if (hash) {
327 		for (idx = 0;; idx++) {
328 			res = rpc_read_node(ht, 1, idx, &ht->root.node);
329 			if (res != TEE_SUCCESS)
330 				return res;
331 
332 			if (!memcmp(ht->root.node.hash, hash,
333 				    sizeof(ht->root.node.hash))) {
334 				res = rpc_read_head(ht, idx, &ht->head);
335 				if (res != TEE_SUCCESS)
336 					return res;
337 				break;
338 			}
339 
340 			if (idx)
341 				return TEE_ERROR_SECURITY;
342 		}
343 	} else {
344 		struct tee_fs_htree_image head[2];
345 
346 		for (idx = 0; idx < 2; idx++) {
347 			res = rpc_read_head(ht, idx, head + idx);
348 			if (res != TEE_SUCCESS)
349 				return res;
350 		}
351 
352 		idx = get_idx_from_counter(head[0].counter, head[1].counter);
353 		if (idx < 0)
354 			return TEE_ERROR_SECURITY;
355 
356 		res = rpc_read_node(ht, 1, idx, &ht->root.node);
357 		if (res != TEE_SUCCESS)
358 			return res;
359 
360 		ht->head = head[idx];
361 	}
362 
363 	ht->root.id = 1;
364 
365 	return TEE_SUCCESS;
366 }
367 
init_tree_from_data(struct tee_fs_htree * ht)368 static TEE_Result init_tree_from_data(struct tee_fs_htree *ht)
369 {
370 	TEE_Result res;
371 	struct tee_fs_htree_node_image node_image;
372 	struct htree_node *node;
373 	struct htree_node *nc;
374 	size_t committed_version;
375 	size_t node_id = 2;
376 
377 	while (node_id <= ht->imeta.max_node_id) {
378 		node = find_node(ht, node_id >> 1);
379 		if (!node)
380 			return TEE_ERROR_GENERIC;
381 		committed_version = !!(node->node.flags &
382 				    HTREE_NODE_COMMITTED_CHILD(node_id & 1));
383 
384 		res = rpc_read_node(ht, node_id, committed_version,
385 				    &node_image);
386 		if (res != TEE_SUCCESS)
387 			return res;
388 
389 		res = get_node(ht, true, node_id, &nc);
390 		if (res != TEE_SUCCESS)
391 			return res;
392 		nc->node = node_image;
393 		node_id++;
394 	}
395 
396 	return TEE_SUCCESS;
397 }
398 
calc_node_hash(struct htree_node * node,struct tee_fs_htree_meta * meta,void * ctx,uint8_t * digest)399 static TEE_Result calc_node_hash(struct htree_node *node,
400 				 struct tee_fs_htree_meta *meta, void *ctx,
401 				 uint8_t *digest)
402 {
403 	TEE_Result res;
404 	uint8_t *ndata = (uint8_t *)&node->node + sizeof(node->node.hash);
405 	size_t nsize = sizeof(node->node) - sizeof(node->node.hash);
406 
407 	res = crypto_hash_init(ctx);
408 	if (res != TEE_SUCCESS)
409 		return res;
410 
411 	res = crypto_hash_update(ctx, ndata, nsize);
412 	if (res != TEE_SUCCESS)
413 		return res;
414 
415 	if (meta) {
416 		res = crypto_hash_update(ctx, (void *)meta, sizeof(*meta));
417 		if (res != TEE_SUCCESS)
418 			return res;
419 	}
420 
421 	if (node->child[0]) {
422 		res = crypto_hash_update(ctx, node->child[0]->node.hash,
423 					 sizeof(node->child[0]->node.hash));
424 		if (res != TEE_SUCCESS)
425 			return res;
426 	}
427 
428 	if (node->child[1]) {
429 		res = crypto_hash_update(ctx, node->child[1]->node.hash,
430 					 sizeof(node->child[1]->node.hash));
431 		if (res != TEE_SUCCESS)
432 			return res;
433 	}
434 
435 	return crypto_hash_final(ctx, digest, TEE_FS_HTREE_HASH_SIZE);
436 }
437 
authenc_init(void ** ctx_ret,TEE_OperationMode mode,struct tee_fs_htree * ht,struct tee_fs_htree_node_image * ni,size_t payload_len)438 static TEE_Result authenc_init(void **ctx_ret, TEE_OperationMode mode,
439 			       struct tee_fs_htree *ht,
440 			       struct tee_fs_htree_node_image *ni,
441 			       size_t payload_len)
442 {
443 	TEE_Result res = TEE_SUCCESS;
444 	const uint32_t alg = TEE_FS_HTREE_AUTH_ENC_ALG;
445 	void *ctx;
446 	size_t aad_len = TEE_FS_HTREE_FEK_SIZE + TEE_FS_HTREE_IV_SIZE;
447 	uint8_t *iv;
448 
449 	if (ni) {
450 		iv = ni->iv;
451 	} else {
452 		iv = ht->head.iv;
453 		aad_len += TEE_FS_HTREE_HASH_SIZE + sizeof(ht->head.counter);
454 	}
455 
456 	if (mode == TEE_MODE_ENCRYPT) {
457 		res = crypto_rng_read(iv, TEE_FS_HTREE_IV_SIZE);
458 		if (res != TEE_SUCCESS)
459 			return res;
460 	}
461 
462 	res = crypto_authenc_alloc_ctx(&ctx, alg);
463 	if (res != TEE_SUCCESS)
464 		return res;
465 
466 	res = crypto_authenc_init(ctx, mode, ht->fek, TEE_FS_HTREE_FEK_SIZE, iv,
467 				  TEE_FS_HTREE_IV_SIZE, TEE_FS_HTREE_TAG_SIZE,
468 				  aad_len, payload_len);
469 	if (res != TEE_SUCCESS)
470 		goto err_free;
471 
472 	if (!ni) {
473 		res = crypto_authenc_update_aad(ctx, mode, ht->root.node.hash,
474 						TEE_FS_HTREE_FEK_SIZE);
475 		if (res != TEE_SUCCESS)
476 			goto err;
477 
478 		res = crypto_authenc_update_aad(ctx, mode,
479 						(void *)&ht->head.counter,
480 						sizeof(ht->head.counter));
481 		if (res != TEE_SUCCESS)
482 			goto err;
483 	}
484 
485 	res = crypto_authenc_update_aad(ctx, mode, ht->head.enc_fek,
486 					TEE_FS_HTREE_FEK_SIZE);
487 	if (res != TEE_SUCCESS)
488 		goto err;
489 
490 	res = crypto_authenc_update_aad(ctx, mode, iv, TEE_FS_HTREE_IV_SIZE);
491 	if (res != TEE_SUCCESS)
492 		goto err;
493 
494 	*ctx_ret = ctx;
495 
496 	return TEE_SUCCESS;
497 err:
498 	crypto_authenc_final(ctx);
499 err_free:
500 	crypto_authenc_free_ctx(ctx);
501 	return res;
502 }
503 
authenc_decrypt_final(void * ctx,const uint8_t * tag,const void * crypt,size_t len,void * plain)504 static TEE_Result authenc_decrypt_final(void *ctx, const uint8_t *tag,
505 					const void *crypt, size_t len,
506 					void *plain)
507 {
508 	TEE_Result res;
509 	size_t out_size = len;
510 
511 	res = crypto_authenc_dec_final(ctx, crypt, len, plain, &out_size, tag,
512 				       TEE_FS_HTREE_TAG_SIZE);
513 	crypto_authenc_final(ctx);
514 	crypto_authenc_free_ctx(ctx);
515 
516 	if (res == TEE_SUCCESS && out_size != len)
517 		return TEE_ERROR_GENERIC;
518 	if (res == TEE_ERROR_MAC_INVALID)
519 		return TEE_ERROR_CORRUPT_OBJECT;
520 
521 	return res;
522 }
523 
authenc_encrypt_final(void * ctx,uint8_t * tag,const void * plain,size_t len,void * crypt)524 static TEE_Result authenc_encrypt_final(void *ctx, uint8_t *tag,
525 					const void *plain, size_t len,
526 					void *crypt)
527 {
528 	TEE_Result res;
529 	size_t out_size = len;
530 	size_t out_tag_size = TEE_FS_HTREE_TAG_SIZE;
531 
532 	res = crypto_authenc_enc_final(ctx, plain, len, crypt, &out_size, tag,
533 				       &out_tag_size);
534 	crypto_authenc_final(ctx);
535 	crypto_authenc_free_ctx(ctx);
536 
537 	if (res == TEE_SUCCESS &&
538 	    (out_size != len || out_tag_size != TEE_FS_HTREE_TAG_SIZE))
539 		return TEE_ERROR_GENERIC;
540 
541 	return res;
542 }
543 
verify_root(struct tee_fs_htree * ht)544 static TEE_Result verify_root(struct tee_fs_htree *ht)
545 {
546 	TEE_Result res;
547 	void *ctx;
548 
549 	res = tee_fs_fek_crypt(ht->uuid, TEE_MODE_DECRYPT, ht->head.enc_fek,
550 			       sizeof(ht->fek), ht->fek);
551 	if (res != TEE_SUCCESS)
552 		return res;
553 
554 	res = authenc_init(&ctx, TEE_MODE_DECRYPT, ht, NULL, sizeof(ht->imeta));
555 	if (res != TEE_SUCCESS)
556 		return res;
557 
558 	return authenc_decrypt_final(ctx, ht->head.tag, ht->head.imeta,
559 				     sizeof(ht->imeta), &ht->imeta);
560 }
561 
verify_node(struct traverse_arg * targ,struct htree_node * node)562 static TEE_Result verify_node(struct traverse_arg *targ,
563 			      struct htree_node *node)
564 {
565 	void *ctx = targ->arg;
566 	TEE_Result res;
567 	uint8_t digest[TEE_FS_HTREE_HASH_SIZE];
568 
569 	if (node->parent)
570 		res = calc_node_hash(node, NULL, ctx, digest);
571 	else
572 		res = calc_node_hash(node, &targ->ht->imeta.meta, ctx, digest);
573 	if (res == TEE_SUCCESS &&
574 	    consttime_memcmp(digest, node->node.hash, sizeof(digest)))
575 		return TEE_ERROR_CORRUPT_OBJECT;
576 
577 	return res;
578 }
579 
verify_tree(struct tee_fs_htree * ht)580 static TEE_Result verify_tree(struct tee_fs_htree *ht)
581 {
582 	TEE_Result res;
583 	void *ctx;
584 
585 	res = crypto_hash_alloc_ctx(&ctx, TEE_FS_HTREE_HASH_ALG);
586 	if (res != TEE_SUCCESS)
587 		return res;
588 
589 	res = htree_traverse_post_order(ht, verify_node, ctx);
590 	crypto_hash_free_ctx(ctx);
591 
592 	return res;
593 }
594 
init_root_node(struct tee_fs_htree * ht)595 static TEE_Result init_root_node(struct tee_fs_htree *ht)
596 {
597 	TEE_Result res;
598 	void *ctx;
599 
600 	res = crypto_hash_alloc_ctx(&ctx, TEE_FS_HTREE_HASH_ALG);
601 	if (res != TEE_SUCCESS)
602 		return res;
603 
604 	ht->root.id = 1;
605 	ht->root.dirty = true;
606 
607 	res = calc_node_hash(&ht->root, &ht->imeta.meta, ctx,
608 			     ht->root.node.hash);
609 	crypto_hash_free_ctx(ctx);
610 
611 	return res;
612 }
613 
tee_fs_htree_open(bool create,uint8_t * hash,const TEE_UUID * uuid,const struct tee_fs_htree_storage * stor,void * stor_aux,struct tee_fs_htree ** ht_ret)614 TEE_Result tee_fs_htree_open(bool create, uint8_t *hash, const TEE_UUID *uuid,
615 			     const struct tee_fs_htree_storage *stor,
616 			     void *stor_aux, struct tee_fs_htree **ht_ret)
617 {
618 	TEE_Result res;
619 	struct tee_fs_htree *ht = calloc(1, sizeof(*ht));
620 
621 	if (!ht)
622 		return TEE_ERROR_OUT_OF_MEMORY;
623 
624 	ht->uuid = uuid;
625 	ht->stor = stor;
626 	ht->stor_aux = stor_aux;
627 
628 	if (create) {
629 		const struct tee_fs_htree_image dummy_head = { .counter = 0 };
630 
631 		res = crypto_rng_read(ht->fek, sizeof(ht->fek));
632 		if (res != TEE_SUCCESS)
633 			goto out;
634 
635 		res = tee_fs_fek_crypt(ht->uuid, TEE_MODE_ENCRYPT, ht->fek,
636 				       sizeof(ht->fek), ht->head.enc_fek);
637 		if (res != TEE_SUCCESS)
638 			goto out;
639 
640 		res = init_root_node(ht);
641 		if (res != TEE_SUCCESS)
642 			goto out;
643 
644 		ht->dirty = true;
645 		res = tee_fs_htree_sync_to_storage(&ht, hash);
646 		if (res != TEE_SUCCESS)
647 			goto out;
648 		res = rpc_write_head(ht, 0, &dummy_head);
649 	} else {
650 		res = init_head_from_data(ht, hash);
651 		if (res != TEE_SUCCESS)
652 			goto out;
653 
654 		res = verify_root(ht);
655 		if (res != TEE_SUCCESS)
656 			goto out;
657 
658 		res = init_tree_from_data(ht);
659 		if (res != TEE_SUCCESS)
660 			goto out;
661 
662 		res = verify_tree(ht);
663 	}
664 out:
665 	if (res == TEE_SUCCESS)
666 		*ht_ret = ht;
667 	else
668 		tee_fs_htree_close(&ht);
669 	return res;
670 }
671 
tee_fs_htree_get_meta(struct tee_fs_htree * ht)672 struct tee_fs_htree_meta *tee_fs_htree_get_meta(struct tee_fs_htree *ht)
673 {
674 	return &ht->imeta.meta;
675 }
676 
tee_fs_htree_meta_set_dirty(struct tee_fs_htree * ht)677 void tee_fs_htree_meta_set_dirty(struct tee_fs_htree *ht)
678 {
679 	ht->dirty = true;
680 	ht->root.dirty = true;
681 }
682 
free_node(struct traverse_arg * targ __unused,struct htree_node * node)683 static TEE_Result free_node(struct traverse_arg *targ __unused,
684 			    struct htree_node *node)
685 {
686 	if (node->parent)
687 		free(node);
688 	return TEE_SUCCESS;
689 }
690 
tee_fs_htree_close(struct tee_fs_htree ** ht)691 void tee_fs_htree_close(struct tee_fs_htree **ht)
692 {
693 	if (!*ht)
694 		return;
695 	htree_traverse_post_order(*ht, free_node, NULL);
696 	free(*ht);
697 	*ht = NULL;
698 }
699 
htree_sync_node_to_storage(struct traverse_arg * targ,struct htree_node * node)700 static TEE_Result htree_sync_node_to_storage(struct traverse_arg *targ,
701 					     struct htree_node *node)
702 {
703 	TEE_Result res;
704 	uint8_t vers;
705 	struct tee_fs_htree_meta *meta = NULL;
706 
707 	/*
708 	 * The node can be dirty while the block isn't updated due to
709 	 * updated children, but if block is updated the node has to be
710 	 * dirty.
711 	 */
712 	assert(node->dirty >= node->block_updated);
713 
714 	if (!node->dirty)
715 		return TEE_SUCCESS;
716 
717 	if (node->parent) {
718 		uint32_t f = HTREE_NODE_COMMITTED_CHILD(node->id & 1);
719 
720 		node->parent->dirty = true;
721 		node->parent->node.flags ^= f;
722 		vers = !!(node->parent->node.flags & f);
723 	} else {
724 		/*
725 		 * Counter isn't updated yet, it's increased just before
726 		 * writing the header.
727 		 */
728 		vers = !(targ->ht->head.counter & 1);
729 		meta = &targ->ht->imeta.meta;
730 	}
731 
732 	res = calc_node_hash(node, meta, targ->arg, node->node.hash);
733 	if (res != TEE_SUCCESS)
734 		return res;
735 
736 	node->dirty = false;
737 	node->block_updated = false;
738 
739 	return rpc_write_node(targ->ht, node->id, vers, &node->node);
740 }
741 
update_root(struct tee_fs_htree * ht)742 static TEE_Result update_root(struct tee_fs_htree *ht)
743 {
744 	TEE_Result res;
745 	void *ctx;
746 
747 	ht->head.counter++;
748 
749 	res = authenc_init(&ctx, TEE_MODE_ENCRYPT, ht, NULL, sizeof(ht->imeta));
750 	if (res != TEE_SUCCESS)
751 		return res;
752 
753 	return authenc_encrypt_final(ctx, ht->head.tag, &ht->imeta,
754 				     sizeof(ht->imeta), &ht->head.imeta);
755 }
756 
tee_fs_htree_sync_to_storage(struct tee_fs_htree ** ht_arg,uint8_t * hash)757 TEE_Result tee_fs_htree_sync_to_storage(struct tee_fs_htree **ht_arg,
758 					uint8_t *hash)
759 {
760 	TEE_Result res;
761 	struct tee_fs_htree *ht = *ht_arg;
762 	void *ctx;
763 
764 	if (!ht)
765 		return TEE_ERROR_CORRUPT_OBJECT;
766 
767 	if (!ht->dirty)
768 		return TEE_SUCCESS;
769 
770 	res = crypto_hash_alloc_ctx(&ctx, TEE_FS_HTREE_HASH_ALG);
771 	if (res != TEE_SUCCESS)
772 		return res;
773 
774 	res = htree_traverse_post_order(ht, htree_sync_node_to_storage, ctx);
775 	if (res != TEE_SUCCESS)
776 		goto out;
777 
778 	/* All the nodes are written to storage now. Time to update root. */
779 	res = update_root(ht);
780 	if (res != TEE_SUCCESS)
781 		goto out;
782 
783 	res = rpc_write_head(ht, ht->head.counter & 1, &ht->head);
784 	if (res != TEE_SUCCESS)
785 		goto out;
786 
787 	ht->dirty = false;
788 	if (hash)
789 		memcpy(hash, ht->root.node.hash, sizeof(ht->root.node.hash));
790 out:
791 	crypto_hash_free_ctx(ctx);
792 	if (res != TEE_SUCCESS)
793 		tee_fs_htree_close(ht_arg);
794 	return res;
795 }
796 
get_block_node(struct tee_fs_htree * ht,bool create,size_t block_num,struct htree_node ** node)797 static TEE_Result get_block_node(struct tee_fs_htree *ht, bool create,
798 				 size_t block_num, struct htree_node **node)
799 {
800 	TEE_Result res;
801 	struct htree_node *nd;
802 
803 	res = get_node(ht, create, BLOCK_NUM_TO_NODE_ID(block_num), &nd);
804 	if (res == TEE_SUCCESS)
805 		*node = nd;
806 
807 	return res;
808 }
809 
tee_fs_htree_write_block(struct tee_fs_htree ** ht_arg,size_t block_num,const void * block)810 TEE_Result tee_fs_htree_write_block(struct tee_fs_htree **ht_arg,
811 				    size_t block_num, const void *block)
812 {
813 	struct tee_fs_htree *ht = *ht_arg;
814 	TEE_Result res;
815 	struct tee_fs_rpc_operation op;
816 	struct htree_node *node = NULL;
817 	uint8_t block_vers;
818 	void *ctx;
819 	void *enc_block;
820 
821 	if (!ht)
822 		return TEE_ERROR_CORRUPT_OBJECT;
823 
824 	res = get_block_node(ht, true, block_num, &node);
825 	if (res != TEE_SUCCESS)
826 		goto out;
827 
828 	if (!node->block_updated)
829 		node->node.flags ^= HTREE_NODE_COMMITTED_BLOCK;
830 
831 	block_vers = !!(node->node.flags & HTREE_NODE_COMMITTED_BLOCK);
832 	res = ht->stor->rpc_write_init(ht->stor_aux, &op,
833 				       TEE_FS_HTREE_TYPE_BLOCK, block_num,
834 				       block_vers, &enc_block);
835 	if (res != TEE_SUCCESS)
836 		goto out;
837 
838 	res = authenc_init(&ctx, TEE_MODE_ENCRYPT, ht, &node->node,
839 			   ht->stor->block_size);
840 	if (res != TEE_SUCCESS)
841 		goto out;
842 	res = authenc_encrypt_final(ctx, node->node.tag, block,
843 				    ht->stor->block_size, enc_block);
844 	if (res != TEE_SUCCESS)
845 		goto out;
846 
847 	res = ht->stor->rpc_write_final(&op);
848 	if (res != TEE_SUCCESS)
849 		goto out;
850 
851 	node->block_updated = true;
852 	node->dirty = true;
853 	ht->dirty = true;
854 out:
855 	if (res != TEE_SUCCESS)
856 		tee_fs_htree_close(ht_arg);
857 	return res;
858 }
859 
tee_fs_htree_read_block(struct tee_fs_htree ** ht_arg,size_t block_num,void * block)860 TEE_Result tee_fs_htree_read_block(struct tee_fs_htree **ht_arg,
861 				   size_t block_num, void *block)
862 {
863 	struct tee_fs_htree *ht = *ht_arg;
864 	TEE_Result res;
865 	struct tee_fs_rpc_operation op;
866 	struct htree_node *node;
867 	uint8_t block_vers;
868 	size_t len;
869 	void *ctx;
870 	void *enc_block;
871 
872 	if (!ht)
873 		return TEE_ERROR_CORRUPT_OBJECT;
874 
875 	res = get_block_node(ht, false, block_num, &node);
876 	if (res != TEE_SUCCESS)
877 		goto out;
878 
879 	block_vers = !!(node->node.flags & HTREE_NODE_COMMITTED_BLOCK);
880 	res = ht->stor->rpc_read_init(ht->stor_aux, &op,
881 				      TEE_FS_HTREE_TYPE_BLOCK, block_num,
882 				      block_vers, &enc_block);
883 	if (res != TEE_SUCCESS)
884 		goto out;
885 
886 	res = ht->stor->rpc_read_final(&op, &len);
887 	if (res != TEE_SUCCESS)
888 		goto out;
889 	if (len != ht->stor->block_size) {
890 		res = TEE_ERROR_CORRUPT_OBJECT;
891 		goto out;
892 	}
893 
894 	res = authenc_init(&ctx, TEE_MODE_DECRYPT, ht, &node->node,
895 			   ht->stor->block_size);
896 	if (res != TEE_SUCCESS)
897 		goto out;
898 
899 	res = authenc_decrypt_final(ctx, node->node.tag, enc_block,
900 				    ht->stor->block_size, block);
901 out:
902 	if (res != TEE_SUCCESS)
903 		tee_fs_htree_close(ht_arg);
904 	return res;
905 }
906 
tee_fs_htree_truncate(struct tee_fs_htree ** ht_arg,size_t block_num)907 TEE_Result tee_fs_htree_truncate(struct tee_fs_htree **ht_arg, size_t block_num)
908 {
909 	struct tee_fs_htree *ht = *ht_arg;
910 	size_t node_id = BLOCK_NUM_TO_NODE_ID(block_num);
911 	struct htree_node *node;
912 
913 	if (!ht)
914 		return TEE_ERROR_CORRUPT_OBJECT;
915 
916 	while (node_id < ht->imeta.max_node_id) {
917 		node = find_closest_node(ht, ht->imeta.max_node_id);
918 		assert(node && node->id == ht->imeta.max_node_id);
919 		assert(!node->child[0] && !node->child[1]);
920 		assert(node->parent);
921 		assert(node->parent->child[node->id & 1] == node);
922 		node->parent->child[node->id & 1] = NULL;
923 		free(node);
924 		ht->imeta.max_node_id--;
925 		ht->dirty = true;
926 	}
927 
928 	return TEE_SUCCESS;
929 }
930