core/tee/fs_htree.c

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