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