core/arch/arm/pta/core_fs_htree_tests.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 <string.h>
  30 #include <tee/fs_htree.h>
  31 #include <tee/tee_fs_rpc.h>
  32 #include <trace.h>
  33 #include <types_ext.h>
  34 #include <util.h>
  35
  36 #include "core_self_tests.h"
  37
  38 /*
  39  * The smallest blocks size that can hold two struct
  40  * tee_fs_htree_node_image or two struct tee_fs_htree_image.
  41  */
  42 #define TEST_BLOCK_SIZE         144
  43
  44 struct test_aux {
  45         uint8_t *data;
  46         size_t data_len;
  47         size_t data_alloced;
  48         uint8_t *block;
  49 };
  50
  51 static TEE_Result test_get_offs_size(enum tee_fs_htree_type type, size_t idx,
  52                                      uint8_t vers, size_t *offs, size_t *size)
  53 {
  54         const size_t node_size = sizeof(struct tee_fs_htree_node_image);
  55         const size_t block_nodes = TEST_BLOCK_SIZE / (node_size * 2);
  56         size_t pbn;
  57         size_t bidx;
  58
  59         COMPILE_TIME_ASSERT(TEST_BLOCK_SIZE >
  60                             sizeof(struct tee_fs_htree_node_image) * 2);
  61         COMPILE_TIME_ASSERT(TEST_BLOCK_SIZE >
  62                             sizeof(struct tee_fs_htree_image) * 2);
  63
  64         assert(vers == 0 || vers == 1);
  65
  66         /*
  67          * File layout
  68          *
  69          * phys block 0:
  70          * tee_fs_htree_image vers 0 @ offs = 0
  71          * tee_fs_htree_image vers 1 @ offs = sizeof(tee_fs_htree_image)
  72          *
  73          * phys block 1:
  74          * tee_fs_htree_node_image 0  vers 0 @ offs = 0
  75          * tee_fs_htree_node_image 0  vers 1 @ offs = node_size
  76          *
  77          * phys block 2:
  78          * data block 0 vers 0
  79          *
  80          * phys block 3:
  81          * tee_fs_htree_node_image 1  vers 0 @ offs = 0
  82          * tee_fs_htree_node_image 1  vers 1 @ offs = node_size
  83          *
  84          * phys block 4:
  85          * data block 0 vers 1
  86          *
  87          * ...
  88          */
  89
  90         switch (type) {
  91         case TEE_FS_HTREE_TYPE_HEAD:
  92                 *offs = sizeof(struct tee_fs_htree_image) * vers;
  93                 *size = sizeof(struct tee_fs_htree_image);
  94                 return TEE_SUCCESS;
  95         case TEE_FS_HTREE_TYPE_NODE:
  96                 pbn = 1 + ((idx / block_nodes) * block_nodes * 2);
  97                 *offs = pbn * TEST_BLOCK_SIZE +
  98                         2 * node_size * (idx % block_nodes) +
  99                         node_size * vers;
 100                 *size = node_size;
 101                 return TEE_SUCCESS;
 102         case TEE_FS_HTREE_TYPE_BLOCK:
 103                 bidx = 2 * idx + vers;
 104                 pbn = 2 + bidx + bidx / (block_nodes * 2 - 1);
 105                 *offs = pbn * TEST_BLOCK_SIZE;
 106                 *size = TEST_BLOCK_SIZE;
 107                 return TEE_SUCCESS;
 108         default:
 109                 return TEE_ERROR_GENERIC;
 110         }
 111 }
 112
 113 static TEE_Result test_read_init(void *aux, struct tee_fs_rpc_operation *op,
 114                                  enum tee_fs_htree_type type, size_t idx,
 115                                  uint8_t vers, void **data)
 116 {
 117         TEE_Result res;
 118         struct test_aux *a = aux;
 119         size_t offs;
 120         size_t sz;
 121
 122         res = test_get_offs_size(type, idx, vers, &offs, &sz);
 123         if (res == TEE_SUCCESS) {
 124                 memset(op, 0, sizeof(*op));
 125                 op->params[0].u.value.a = (vaddr_t)aux;
 126                 op->params[0].u.value.b = offs;
 127                 op->params[0].u.value.c = sz;
 128                 *data = a->block;
 129         }
 130
 131         return res;
 132 }
 133
 134 static void *uint_to_ptr(uintptr_t p)
 135 {
 136         return (void *)p;
 137 }
 138
 139 static TEE_Result test_read_final(struct tee_fs_rpc_operation *op,
 140                                   size_t *bytes)
 141 {
 142         struct test_aux *a = uint_to_ptr(op->params[0].u.value.a);
 143         size_t offs = op->params[0].u.value.b;
 144         size_t sz = op->params[0].u.value.c;
 145
 146         if (offs + sz <= a->data_len)
 147                 *bytes = sz;
 148         else if (offs <= a->data_len)
 149                 *bytes = a->data_len - offs;
 150         else
 151                 *bytes = 0;
 152
 153         memcpy(a->block, a->data + offs, *bytes);
 154         return TEE_SUCCESS;
 155 }
 156
 157 static TEE_Result test_write_init(void *aux, struct tee_fs_rpc_operation *op,
 158                                   enum tee_fs_htree_type type, size_t idx,
 159                                   uint8_t vers, void **data)
 160 {
 161         return test_read_init(aux, op, type, idx, vers, data);
 162 }
 163
 164 static TEE_Result test_write_final(struct tee_fs_rpc_operation *op)
 165 {
 166         struct test_aux *a = uint_to_ptr(op->params[0].u.value.a);
 167         size_t offs = op->params[0].u.value.b;
 168         size_t sz = op->params[0].u.value.c;
 169         size_t end = offs + sz;
 170
 171         if (end > a->data_alloced) {
 172                 EMSG("out of bounds");
 173                 return TEE_ERROR_GENERIC;
 174         }
 175
 176         memcpy(a->data + offs, a->block, sz);
 177         if (end > a->data_len)
 178                 a->data_len = end;
 179         return TEE_SUCCESS;
 180
 181 }
 182
 183 static const struct tee_fs_htree_storage test_htree_ops = {
 184         .block_size = TEST_BLOCK_SIZE,
 185         .rpc_read_init = test_read_init,
 186         .rpc_read_final = test_read_final,
 187         .rpc_write_init = test_write_init,
 188         .rpc_write_final = test_write_final,
 189 };
 190
 191 #define CHECK_RES(res, cleanup)                                         \
 192                 do {                                                    \
 193                         TEE_Result _res = (res);                        \
 194                                                                         \
 195                         if (_res != TEE_SUCCESS) {                      \
 196                                 EMSG("error: res = %#" PRIx32, _res);   \
 197                                 { cleanup; }                            \
 198                         }                                               \
 199                 } while (0)
 200
 201 static uint32_t val_from_bn_n_salt(size_t bn, size_t n, uint8_t salt)
 202 {
 203         assert(bn < UINT16_MAX);
 204         assert(n < UINT8_MAX);
 205         return SHIFT_U32(n, 16) | SHIFT_U32(bn, 8) | salt;
 206 }
 207
 208 static TEE_Result write_block(struct tee_fs_htree **ht, size_t bn, uint8_t salt)
 209 {
 210         uint32_t b[TEST_BLOCK_SIZE / sizeof(uint32_t)];
 211         size_t n;
 212
 213         for (n = 0; n < ARRAY_SIZE(b); n++)
 214                 b[n] = val_from_bn_n_salt(bn, n, salt);
 215
 216         return tee_fs_htree_write_block(ht, bn, b);
 217 }
 218
 219 static TEE_Result read_block(struct tee_fs_htree **ht, size_t bn, uint8_t salt)
 220 {
 221         TEE_Result res;
 222         uint32_t b[TEST_BLOCK_SIZE / sizeof(uint32_t)];
 223         size_t n;
 224
 225         res = tee_fs_htree_read_block(ht, bn, b);
 226         if (res != TEE_SUCCESS)
 227                 return res;
 228
 229         for (n = 0; n < ARRAY_SIZE(b); n++) {
 230                 if (b[n] != val_from_bn_n_salt(bn, n, salt)) {
 231                         DMSG("Unpected b[%zu] %#" PRIx32
 232                              "(expected %#" PRIx32 ")",
 233                              n, b[n], val_from_bn_n_salt(bn, n, salt));
 234                         return TEE_ERROR_SECURITY;
 235                 }
 236         }
 237
 238         return TEE_SUCCESS;
 239 }
 240
 241 static TEE_Result do_range(TEE_Result (*fn)(struct tee_fs_htree **ht,
 242                                             size_t bn, uint8_t salt),
 243                            struct tee_fs_htree **ht, size_t begin,
 244                            size_t num_blocks, size_t salt)
 245 {
 246         TEE_Result res = TEE_SUCCESS;
 247         size_t n;
 248
 249         for (n = 0; n < num_blocks; n++) {
 250                 res = fn(ht, n + begin, salt);
 251                 CHECK_RES(res, goto out);
 252         }
 253
 254 out:
 255         return res;
 256 }
 257
 258 static TEE_Result do_range_backwards(TEE_Result (*fn)(struct tee_fs_htree **ht,
 259                                                       size_t bn, uint8_t salt),
 260                                      struct tee_fs_htree **ht, size_t begin,
 261                                      size_t num_blocks, size_t salt)
 262 {
 263         TEE_Result res = TEE_SUCCESS;
 264         size_t n;
 265
 266         for (n = 0; n < num_blocks; n++) {
 267                 res = fn(ht, num_blocks - 1 - n + begin, salt);
 268                 CHECK_RES(res, goto out);
 269         }
 270
 271 out:
 272         return res;
 273 }
 274
 275 static TEE_Result htree_test_rewrite(struct test_aux *aux, size_t num_blocks,
 276                                      size_t w_unsync_begin, size_t w_unsync_num)
 277 {
 278         TEE_Result res;
 279         struct tee_fs_htree *ht = NULL;
 280         size_t salt = 23;
 281
 282         assert((w_unsync_begin + w_unsync_num) <= num_blocks);
 283
 284         aux->data_len = 0;
 285         memset(aux->data, 0xce, aux->data_alloced);
 286
 287         res = tee_fs_htree_open(true, &test_htree_ops, aux, &ht);
 288         CHECK_RES(res, goto out);
 289
 290         /*
 291          * Intialize all blocks and verify that they read back as
 292          * expected.
 293          */
 294         res = do_range(write_block, &ht, 0, num_blocks, salt);
 295         CHECK_RES(res, goto out);
 296
 297         res = do_range(read_block, &ht, 0, num_blocks, salt);
 298         CHECK_RES(res, goto out);
 299
 300         /*
 301          * Write all blocks again, but starting from the end using a new
 302          * salt, then verify that that read back as expected.
 303          */
 304         salt++;
 305         res = do_range_backwards(write_block, &ht, 0, num_blocks, salt);
 306         CHECK_RES(res, goto out);
 307
 308         res = do_range(read_block, &ht, 0, num_blocks, salt);
 309         CHECK_RES(res, goto out);
 310
 311         /*
 312          * Use a new salt to write all blocks once more and verify that
 313          * they read back as expected.
 314          */
 315         salt++;
 316         res = do_range(write_block, &ht, 0, num_blocks, salt);
 317         CHECK_RES(res, goto out);
 318
 319         res = do_range(read_block, &ht, 0, num_blocks, salt);
 320         CHECK_RES(res, goto out);
 321
 322         /*
 323          * Sync the changes of the nodes to memory, verify that all
 324          * blocks are read back as expected.
 325          */
 326         res = tee_fs_htree_sync_to_storage(&ht);
 327         CHECK_RES(res, goto out);
 328
 329         res = do_range(read_block, &ht, 0, num_blocks, salt);
 330         CHECK_RES(res, goto out);
 331
 332         /*
 333          * Close and reopen the hash-tree
 334          */
 335         tee_fs_htree_close(&ht);
 336         res = tee_fs_htree_open(false, &test_htree_ops, aux, &ht);
 337         CHECK_RES(res, goto out);
 338
 339         /*
 340          * Verify that all blocks are read as expected.
 341          */
 342         res = do_range(read_block, &ht, 0, num_blocks, salt);
 343         CHECK_RES(res, goto out);
 344
 345         /*
 346          * Rewrite a few blocks and verify that all blocks are read as
 347          * expected.
 348          */
 349         res = do_range_backwards(write_block, &ht, w_unsync_begin, w_unsync_num,
 350                                  salt + 1);
 351         CHECK_RES(res, goto out);
 352
 353         res = do_range(read_block, &ht, 0, w_unsync_begin, salt);
 354         CHECK_RES(res, goto out);
 355         res = do_range(read_block, &ht, w_unsync_begin, w_unsync_num, salt + 1);
 356         CHECK_RES(res, goto out);
 357         res = do_range(read_block, &ht, w_unsync_begin + w_unsync_num,
 358                         num_blocks - (w_unsync_begin + w_unsync_num), salt);
 359         CHECK_RES(res, goto out);
 360
 361         /*
 362          * Rewrite the blocks from above again with another salt and
 363          * verify that they are read back as expected.
 364          */
 365         res = do_range(write_block, &ht, w_unsync_begin, w_unsync_num,
 366                        salt + 2);
 367         CHECK_RES(res, goto out);
 368
 369         res = do_range(read_block, &ht, 0, w_unsync_begin, salt);
 370         CHECK_RES(res, goto out);
 371         res = do_range(read_block, &ht, w_unsync_begin, w_unsync_num, salt + 2);
 372         CHECK_RES(res, goto out);
 373         res = do_range(read_block, &ht, w_unsync_begin + w_unsync_num,
 374                         num_blocks - (w_unsync_begin + w_unsync_num), salt);
 375         CHECK_RES(res, goto out);
 376
 377         /*
 378          * Skip tee_fs_htree_sync_to_storage() and call
 379          * tee_fs_htree_close() directly to undo the changes since last
 380          * call to tee_fs_htree_sync_to_storage().  Reopen the hash-tree
 381          * and verify that recent changes indeed was discarded.
 382          */
 383         tee_fs_htree_close(&ht);
 384         res = tee_fs_htree_open(false, &test_htree_ops, aux, &ht);
 385         CHECK_RES(res, goto out);
 386
 387         res = do_range(read_block, &ht, 0, num_blocks, salt);
 388         CHECK_RES(res, goto out);
 389
 390         /*
 391          * Close, reopen and verify that all blocks are read as expected
 392          * again.
 393          */
 394         tee_fs_htree_close(&ht);
 395         res = tee_fs_htree_open(false, &test_htree_ops, aux, &ht);
 396         CHECK_RES(res, goto out);
 397
 398         res = do_range(read_block, &ht, 0, num_blocks, salt);
 399         CHECK_RES(res, goto out);
 400
 401 out:
 402         tee_fs_htree_close(&ht);
 403         return res;
 404 }
 405
 406 TEE_Result core_fs_htree_tests(uint32_t nParamTypes,
 407                                TEE_Param pParams[TEE_NUM_PARAMS] __unused)
 408 {
 409         TEE_Result res;
 410         struct test_aux aux;
 411         size_t num_blocks = 10;
 412         size_t offs;
 413         size_t sz;
 414         size_t n;
 415         size_t m;
 416         size_t o;
 417
 418         if (nParamTypes)
 419                 return TEE_ERROR_BAD_PARAMETERS;
 420
 421         res = test_get_offs_size(TEE_FS_HTREE_TYPE_BLOCK, num_blocks, 1,
 422                                  &offs, &sz);
 423         CHECK_RES(res, return res);
 424
 425         aux.data_alloced = offs + sz;
 426         aux.data = malloc(aux.data_alloced);
 427         aux.block = malloc(TEST_BLOCK_SIZE);
 428         if (!aux.data || !aux.block) {
 429                 res = TEE_ERROR_OUT_OF_MEMORY;
 430                 goto out;
 431         }
 432
 433         /*
 434          * n is the number of block we're going to initialize/use.
 435          * m is the offset from where we'll rewrite blocks and expect
 436          * the changes to be visible until tee_fs_htree_close() is called
 437          * without a call to tee_fs_htree_sync_to_storage() before.
 438          * o is the number of blocks we're rewriting starting at m.
 439          */
 440         for (n = 0; n < num_blocks; n += 3) {
 441                 for (m = 0; m < n; m += 3) {
 442                         for (o = 0; o < (n - m); o++) {
 443                                 res = htree_test_rewrite(&aux, n, m, o);
 444                                 CHECK_RES(res, goto out);
 445                                 o += 2;
 446                         }
 447                 }
 448         }
 449
 450
 451 out:
 452         free(aux.data);
 453         free(aux.block);
 454         return res;
 455 }
 456