liblttng-ust/lttng-filter-validator.c

   1 /*
   2  * lttng-filter-validator.c
   3  *
   4  * LTTng UST filter bytecode validator.
   5  *
   6  * Copyright (C) 2010-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; only
  11  * version 2.1 of the License.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 #define _LGPL_SOURCE
  24 #include <urcu-bp.h>
  25 #include <time.h>
  26 #include "lttng-filter.h"
  27
  28 #include <urcu/rculfhash.h>
  29 #include "lttng-hash-helper.h"
  30
  31 /*
  32  * Number of merge points for hash table size. Hash table initialized to
  33  * that size, and we do not resize, because we do not want to trigger
  34  * RCU worker thread execution: fall-back on linear traversal if number
  35  * of merge points exceeds this value.
  36  */
  37 #define DEFAULT_NR_MERGE_POINTS         128
  38 #define MIN_NR_BUCKETS                  128
  39 #define MAX_NR_BUCKETS                  128
  40
  41 /* merge point table node */
  42 struct lfht_mp_node {
  43         struct cds_lfht_node node;
  44
  45         /* Context at merge point */
  46         struct vstack stack;
  47         unsigned long target_pc;
  48 };
  49
  50 static unsigned long lttng_hash_seed;
  51 static unsigned int lttng_hash_seed_ready;
  52
  53 static
  54 int lttng_hash_match(struct cds_lfht_node *node, const void *key)
  55 {
  56         struct lfht_mp_node *mp_node =
  57                 caa_container_of(node, struct lfht_mp_node, node);
  58         unsigned long key_pc = (unsigned long) key;
  59
  60         if (mp_node->target_pc == key_pc)
  61                 return 1;
  62         else
  63                 return 0;
  64 }
  65
  66 static
  67 int merge_point_add(struct cds_lfht *ht, unsigned long target_pc,
  68                 const struct vstack *stack)
  69 {
  70         struct lfht_mp_node *node;
  71         unsigned long hash = lttng_hash_mix((const void *) target_pc,
  72                                 sizeof(target_pc),
  73                                 lttng_hash_seed);
  74
  75         dbg_printf("Filter: adding merge point at offset %lu, hash %lu\n",
  76                         target_pc, hash);
  77         node = zmalloc(sizeof(struct lfht_mp_node));
  78         if (!node)
  79                 return -ENOMEM;
  80         node->target_pc = target_pc;
  81         memcpy(&node->stack, stack, sizeof(node->stack));
  82         cds_lfht_add(ht, hash, &node->node);
  83         return 0;
  84 }
  85
  86 /*
  87  * Binary comparators use top of stack and top of stack -1.
  88  */
  89 static
  90 int bin_op_compare_check(struct vstack *stack, const char *str)
  91 {
  92         if (unlikely(!vstack_ax(stack) || !vstack_bx(stack)))
  93                 goto error_unknown;
  94
  95         switch (vstack_ax(stack)->type) {
  96         default:
  97                 goto error_unknown;
  98
  99         case REG_STRING:
 100                 switch (vstack_bx(stack)->type) {
 101                 default:
 102                         goto error_unknown;
 103
 104                 case REG_STRING:
 105                         break;
 106                 case REG_S64:
 107                 case REG_DOUBLE:
 108                         goto error_mismatch;
 109                 }
 110                 break;
 111         case REG_S64:
 112         case REG_DOUBLE:
 113                 switch (vstack_bx(stack)->type) {
 114                 default:
 115                         goto error_unknown;
 116
 117                 case REG_STRING:
 118                         goto error_mismatch;
 119
 120                 case REG_S64:
 121                 case REG_DOUBLE:
 122                         break;
 123                 }
 124                 break;
 125         }
 126         return 0;
 127
 128 error_unknown:
 129         return -EINVAL;
 130
 131 error_mismatch:
 132         ERR("type mismatch for '%s' binary operator\n", str);
 133         return -EINVAL;
 134 }
 135
 136 /*
 137  * Validate bytecode range overflow within the validation pass.
 138  * Called for each instruction encountered.
 139  */
 140 static
 141 int bytecode_validate_overflow(struct bytecode_runtime *bytecode,
 142                 void *start_pc, void *pc)
 143 {
 144         int ret = 0;
 145
 146         switch (*(filter_opcode_t *) pc) {
 147         case FILTER_OP_UNKNOWN:
 148         default:
 149         {
 150                 ERR("unknown bytecode op %u\n",
 151                         (unsigned int) *(filter_opcode_t *) pc);
 152                 ret = -EINVAL;
 153                 break;
 154         }
 155
 156         case FILTER_OP_RETURN:
 157         {
 158                 if (unlikely(pc + sizeof(struct return_op)
 159                                 > start_pc + bytecode->len)) {
 160                         ret = -EINVAL;
 161                 }
 162                 break;
 163         }
 164
 165         /* binary */
 166         case FILTER_OP_MUL:
 167         case FILTER_OP_DIV:
 168         case FILTER_OP_MOD:
 169         case FILTER_OP_PLUS:
 170         case FILTER_OP_MINUS:
 171         case FILTER_OP_RSHIFT:
 172         case FILTER_OP_LSHIFT:
 173         case FILTER_OP_BIN_AND:
 174         case FILTER_OP_BIN_OR:
 175         case FILTER_OP_BIN_XOR:
 176         {
 177                 ERR("unsupported bytecode op %u\n",
 178                         (unsigned int) *(filter_opcode_t *) pc);
 179                 ret = -EINVAL;
 180                 break;
 181         }
 182
 183         case FILTER_OP_EQ:
 184         case FILTER_OP_NE:
 185         case FILTER_OP_GT:
 186         case FILTER_OP_LT:
 187         case FILTER_OP_GE:
 188         case FILTER_OP_LE:
 189         case FILTER_OP_EQ_STRING:
 190         case FILTER_OP_NE_STRING:
 191         case FILTER_OP_GT_STRING:
 192         case FILTER_OP_LT_STRING:
 193         case FILTER_OP_GE_STRING:
 194         case FILTER_OP_LE_STRING:
 195         case FILTER_OP_EQ_S64:
 196         case FILTER_OP_NE_S64:
 197         case FILTER_OP_GT_S64:
 198         case FILTER_OP_LT_S64:
 199         case FILTER_OP_GE_S64:
 200         case FILTER_OP_LE_S64:
 201         case FILTER_OP_EQ_DOUBLE:
 202         case FILTER_OP_NE_DOUBLE:
 203         case FILTER_OP_GT_DOUBLE:
 204         case FILTER_OP_LT_DOUBLE:
 205         case FILTER_OP_GE_DOUBLE:
 206         case FILTER_OP_LE_DOUBLE:
 207         {
 208                 if (unlikely(pc + sizeof(struct binary_op)
 209                                 > start_pc + bytecode->len)) {
 210                         ret = -EINVAL;
 211                 }
 212                 break;
 213         }
 214
 215         /* unary */
 216         case FILTER_OP_UNARY_PLUS:
 217         case FILTER_OP_UNARY_MINUS:
 218         case FILTER_OP_UNARY_NOT:
 219         case FILTER_OP_UNARY_PLUS_S64:
 220         case FILTER_OP_UNARY_MINUS_S64:
 221         case FILTER_OP_UNARY_NOT_S64:
 222         case FILTER_OP_UNARY_PLUS_DOUBLE:
 223         case FILTER_OP_UNARY_MINUS_DOUBLE:
 224         case FILTER_OP_UNARY_NOT_DOUBLE:
 225         {
 226                 if (unlikely(pc + sizeof(struct unary_op)
 227                                 > start_pc + bytecode->len)) {
 228                         ret = -EINVAL;
 229                 }
 230                 break;
 231         }
 232
 233         /* logical */
 234         case FILTER_OP_AND:
 235         case FILTER_OP_OR:
 236         {
 237                 if (unlikely(pc + sizeof(struct logical_op)
 238                                 > start_pc + bytecode->len)) {
 239                         ret = -EINVAL;
 240                 }
 241                 break;
 242         }
 243
 244         /* load */
 245         case FILTER_OP_LOAD_FIELD_REF:
 246         {
 247                 ERR("Unknown field ref type\n");
 248                 ret = -EINVAL;
 249                 break;
 250         }
 251         case FILTER_OP_LOAD_FIELD_REF_STRING:
 252         case FILTER_OP_LOAD_FIELD_REF_SEQUENCE:
 253         case FILTER_OP_LOAD_FIELD_REF_S64:
 254         case FILTER_OP_LOAD_FIELD_REF_DOUBLE:
 255         {
 256                 if (unlikely(pc + sizeof(struct load_op) + sizeof(struct field_ref)
 257                                 > start_pc + bytecode->len)) {
 258                         ret = -EINVAL;
 259                 }
 260                 break;
 261         }
 262
 263         case FILTER_OP_LOAD_STRING:
 264         {
 265                 struct load_op *insn = (struct load_op *) pc;
 266                 uint32_t str_len, maxlen;
 267
 268                 if (unlikely(pc + sizeof(struct load_op)
 269                                 > start_pc + bytecode->len)) {
 270                         ret = -EINVAL;
 271                         break;
 272                 }
 273
 274                 maxlen = start_pc + bytecode->len - pc - sizeof(struct load_op);
 275                 str_len = strnlen(insn->data, maxlen);
 276                 if (unlikely(str_len >= maxlen)) {
 277                         /* Final '\0' not found within range */
 278                         ret = -EINVAL;
 279                 }
 280                 break;
 281         }
 282
 283         case FILTER_OP_LOAD_S64:
 284         {
 285                 if (unlikely(pc + sizeof(struct load_op) + sizeof(struct literal_numeric)
 286                                 > start_pc + bytecode->len)) {
 287                         ret = -EINVAL;
 288                 }
 289                 break;
 290         }
 291
 292         case FILTER_OP_LOAD_DOUBLE:
 293         {
 294                 if (unlikely(pc + sizeof(struct load_op) + sizeof(struct literal_double)
 295                                 > start_pc + bytecode->len)) {
 296                         ret = -EINVAL;
 297                 }
 298                 break;
 299         }
 300
 301         case FILTER_OP_CAST_TO_S64:
 302         case FILTER_OP_CAST_DOUBLE_TO_S64:
 303         case FILTER_OP_CAST_NOP:
 304         {
 305                 if (unlikely(pc + sizeof(struct cast_op)
 306                                 > start_pc + bytecode->len)) {
 307                         ret = -EINVAL;
 308                 }
 309                 break;
 310         }
 311         }
 312
 313         return ret;
 314 }
 315
 316 static
 317 unsigned long delete_all_nodes(struct cds_lfht *ht)
 318 {
 319         struct cds_lfht_iter iter;
 320         struct lfht_mp_node *node;
 321         unsigned long nr_nodes = 0;
 322
 323         cds_lfht_for_each_entry(ht, &iter, node, node) {
 324                 int ret;
 325
 326                 ret = cds_lfht_del(ht, cds_lfht_iter_get_node(&iter));
 327                 assert(!ret);
 328                 /* note: this hash table is never used concurrently */
 329                 free(node);
 330                 nr_nodes++;
 331         }
 332         return nr_nodes;
 333 }
 334
 335 /*
 336  * Return value:
 337  * 0: success
 338  * <0: error
 339  */
 340 static
 341 int validate_instruction_context(struct bytecode_runtime *bytecode,
 342                 struct vstack *stack,
 343                 void *start_pc,
 344                 void *pc)
 345 {
 346         int ret = 0;
 347
 348         switch (*(filter_opcode_t *) pc) {
 349         case FILTER_OP_UNKNOWN:
 350         default:
 351         {
 352                 ERR("unknown bytecode op %u\n",
 353                         (unsigned int) *(filter_opcode_t *) pc);
 354                 ret = -EINVAL;
 355                 goto end;
 356         }
 357
 358         case FILTER_OP_RETURN:
 359         {
 360                 goto end;
 361         }
 362
 363         /* binary */
 364         case FILTER_OP_MUL:
 365         case FILTER_OP_DIV:
 366         case FILTER_OP_MOD:
 367         case FILTER_OP_PLUS:
 368         case FILTER_OP_MINUS:
 369         case FILTER_OP_RSHIFT:
 370         case FILTER_OP_LSHIFT:
 371         case FILTER_OP_BIN_AND:
 372         case FILTER_OP_BIN_OR:
 373         case FILTER_OP_BIN_XOR:
 374         {
 375                 ERR("unsupported bytecode op %u\n",
 376                         (unsigned int) *(filter_opcode_t *) pc);
 377                 ret = -EINVAL;
 378                 goto end;
 379         }
 380
 381         case FILTER_OP_EQ:
 382         {
 383                 ret = bin_op_compare_check(stack, "==");
 384                 if (ret)
 385                         goto end;
 386                 break;
 387         }
 388         case FILTER_OP_NE:
 389         {
 390                 ret = bin_op_compare_check(stack, "!=");
 391                 if (ret)
 392                         goto end;
 393                 break;
 394         }
 395         case FILTER_OP_GT:
 396         {
 397                 ret = bin_op_compare_check(stack, ">");
 398                 if (ret)
 399                         goto end;
 400                 break;
 401         }
 402         case FILTER_OP_LT:
 403         {
 404                 ret = bin_op_compare_check(stack, "<");
 405                 if (ret)
 406                         goto end;
 407                 break;
 408         }
 409         case FILTER_OP_GE:
 410         {
 411                 ret = bin_op_compare_check(stack, ">=");
 412                 if (ret)
 413                         goto end;
 414                 break;
 415         }
 416         case FILTER_OP_LE:
 417         {
 418                 ret = bin_op_compare_check(stack, "<=");
 419                 if (ret)
 420                         goto end;
 421                 break;
 422         }
 423
 424         case FILTER_OP_EQ_STRING:
 425         case FILTER_OP_NE_STRING:
 426         case FILTER_OP_GT_STRING:
 427         case FILTER_OP_LT_STRING:
 428         case FILTER_OP_GE_STRING:
 429         case FILTER_OP_LE_STRING:
 430         {
 431                 if (!vstack_ax(stack) || !vstack_bx(stack)) {
 432                         ERR("Empty stack\n");
 433                         ret = -EINVAL;
 434                         goto end;
 435                 }
 436                 if (vstack_ax(stack)->type != REG_STRING
 437                                 || vstack_bx(stack)->type != REG_STRING) {
 438                         ERR("Unexpected register type for string comparator\n");
 439                         ret = -EINVAL;
 440                         goto end;
 441                 }
 442                 break;
 443         }
 444
 445         case FILTER_OP_EQ_S64:
 446         case FILTER_OP_NE_S64:
 447         case FILTER_OP_GT_S64:
 448         case FILTER_OP_LT_S64:
 449         case FILTER_OP_GE_S64:
 450         case FILTER_OP_LE_S64:
 451         {
 452                 if (!vstack_ax(stack) || !vstack_bx(stack)) {
 453                         ERR("Empty stack\n");
 454                         ret = -EINVAL;
 455                         goto end;
 456                 }
 457                 if (vstack_ax(stack)->type != REG_S64
 458                                 || vstack_bx(stack)->type != REG_S64) {
 459                         ERR("Unexpected register type for s64 comparator\n");
 460                         ret = -EINVAL;
 461                         goto end;
 462                 }
 463                 break;
 464         }
 465
 466         case FILTER_OP_EQ_DOUBLE:
 467         case FILTER_OP_NE_DOUBLE:
 468         case FILTER_OP_GT_DOUBLE:
 469         case FILTER_OP_LT_DOUBLE:
 470         case FILTER_OP_GE_DOUBLE:
 471         case FILTER_OP_LE_DOUBLE:
 472         {
 473                 if (!vstack_ax(stack) || !vstack_bx(stack)) {
 474                         ERR("Empty stack\n");
 475                         ret = -EINVAL;
 476                         goto end;
 477                 }
 478                 if ((vstack_ax(stack)->type != REG_DOUBLE && vstack_ax(stack)->type != REG_S64)
 479                                 || (vstack_bx(stack)-> type != REG_DOUBLE && vstack_bx(stack)->type != REG_S64)) {
 480                         ERR("Unexpected register type for double comparator\n");
 481                         ret = -EINVAL;
 482                         goto end;
 483                 }
 484                 if (vstack_ax(stack)->type != REG_DOUBLE && vstack_bx(stack)->type != REG_DOUBLE) {
 485                         ERR("Double operator should have at least one double register\n");
 486                         ret = -EINVAL;
 487                         goto end;
 488                 }
 489                 break;
 490         }
 491
 492         /* unary */
 493         case FILTER_OP_UNARY_PLUS:
 494         case FILTER_OP_UNARY_MINUS:
 495         case FILTER_OP_UNARY_NOT:
 496         {
 497                 if (!vstack_ax(stack)) {
 498                         ERR("Empty stack\n");
 499                         ret = -EINVAL;
 500                         goto end;
 501                 }
 502                 switch (vstack_ax(stack)->type) {
 503                 default:
 504                         ERR("unknown register type\n");
 505                         ret = -EINVAL;
 506                         goto end;
 507
 508                 case REG_STRING:
 509                         ERR("Unary op can only be applied to numeric or floating point registers\n");
 510                         ret = -EINVAL;
 511                         goto end;
 512                 case REG_S64:
 513                         break;
 514                 case REG_DOUBLE:
 515                         break;
 516                 }
 517                 break;
 518         }
 519
 520         case FILTER_OP_UNARY_PLUS_S64:
 521         case FILTER_OP_UNARY_MINUS_S64:
 522         case FILTER_OP_UNARY_NOT_S64:
 523         {
 524                 if (!vstack_ax(stack)) {
 525                         ERR("Empty stack\n");
 526                         ret = -EINVAL;
 527                         goto end;
 528                 }
 529                 if (vstack_ax(stack)->type != REG_S64) {
 530                         ERR("Invalid register type\n");
 531                         ret = -EINVAL;
 532                         goto end;
 533                 }
 534                 break;
 535         }
 536
 537         case FILTER_OP_UNARY_PLUS_DOUBLE:
 538         case FILTER_OP_UNARY_MINUS_DOUBLE:
 539         case FILTER_OP_UNARY_NOT_DOUBLE:
 540         {
 541                 if (!vstack_ax(stack)) {
 542                         ERR("Empty stack\n");
 543                         ret = -EINVAL;
 544                         goto end;
 545                 }
 546                 if (vstack_ax(stack)->type != REG_DOUBLE) {
 547                         ERR("Invalid register type\n");
 548                         ret = -EINVAL;
 549                         goto end;
 550                 }
 551                 break;
 552         }
 553
 554         /* logical */
 555         case FILTER_OP_AND:
 556         case FILTER_OP_OR:
 557         {
 558                 struct logical_op *insn = (struct logical_op *) pc;
 559
 560                 if (!vstack_ax(stack)) {
 561                         ERR("Empty stack\n");
 562                         ret = -EINVAL;
 563                         goto end;
 564                 }
 565                 if (vstack_ax(stack)->type != REG_S64) {
 566                         ERR("Logical comparator expects S64 register\n");
 567                         ret = -EINVAL;
 568                         goto end;
 569                 }
 570
 571                 dbg_printf("Validate jumping to bytecode offset %u\n",
 572                         (unsigned int) insn->skip_offset);
 573                 if (unlikely(start_pc + insn->skip_offset <= pc)) {
 574                         ERR("Loops are not allowed in bytecode\n");
 575                         ret = -EINVAL;
 576                         goto end;
 577                 }
 578                 break;
 579         }
 580
 581         /* load */
 582         case FILTER_OP_LOAD_FIELD_REF:
 583         {
 584                 ERR("Unknown field ref type\n");
 585                 ret = -EINVAL;
 586                 goto end;
 587         }
 588         case FILTER_OP_LOAD_FIELD_REF_STRING:
 589         case FILTER_OP_LOAD_FIELD_REF_SEQUENCE:
 590         {
 591                 struct load_op *insn = (struct load_op *) pc;
 592                 struct field_ref *ref = (struct field_ref *) insn->data;
 593
 594                 dbg_printf("Validate load field ref offset %u type string\n",
 595                         ref->offset);
 596                 break;
 597         }
 598         case FILTER_OP_LOAD_FIELD_REF_S64:
 599         {
 600                 struct load_op *insn = (struct load_op *) pc;
 601                 struct field_ref *ref = (struct field_ref *) insn->data;
 602
 603                 dbg_printf("Validate load field ref offset %u type s64\n",
 604                         ref->offset);
 605                 break;
 606         }
 607         case FILTER_OP_LOAD_FIELD_REF_DOUBLE:
 608         {
 609                 struct load_op *insn = (struct load_op *) pc;
 610                 struct field_ref *ref = (struct field_ref *) insn->data;
 611
 612                 dbg_printf("Validate load field ref offset %u type double\n",
 613                         ref->offset);
 614                 break;
 615         }
 616
 617         case FILTER_OP_LOAD_STRING:
 618         {
 619                 break;
 620         }
 621
 622         case FILTER_OP_LOAD_S64:
 623         {
 624                 break;
 625         }
 626
 627         case FILTER_OP_LOAD_DOUBLE:
 628         {
 629                 break;
 630         }
 631
 632         case FILTER_OP_CAST_TO_S64:
 633         case FILTER_OP_CAST_DOUBLE_TO_S64:
 634         {
 635                 struct cast_op *insn = (struct cast_op *) pc;
 636
 637                 if (!vstack_ax(stack)) {
 638                         ERR("Empty stack\n");
 639                         ret = -EINVAL;
 640                         goto end;
 641                 }
 642                 switch (vstack_ax(stack)->type) {
 643                 default:
 644                         ERR("unknown register type\n");
 645                         ret = -EINVAL;
 646                         goto end;
 647
 648                 case REG_STRING:
 649                         ERR("Cast op can only be applied to numeric or floating point registers\n");
 650                         ret = -EINVAL;
 651                         goto end;
 652                 case REG_S64:
 653                         break;
 654                 case REG_DOUBLE:
 655                         break;
 656                 }
 657                 if (insn->op == FILTER_OP_CAST_DOUBLE_TO_S64) {
 658                         if (vstack_ax(stack)->type != REG_DOUBLE) {
 659                                 ERR("Cast expects double\n");
 660                                 ret = -EINVAL;
 661                                 goto end;
 662                         }
 663                 }
 664                 break;
 665         }
 666         case FILTER_OP_CAST_NOP:
 667         {
 668                 break;
 669         }
 670
 671         }
 672 end:
 673         return ret;
 674 }
 675
 676 /*
 677  * Return value:
 678  * 0: success
 679  * <0: error
 680  */
 681 static
 682 int validate_instruction_all_contexts(struct bytecode_runtime *bytecode,
 683                 struct cds_lfht *merge_points,
 684                 struct vstack *stack,
 685                 void *start_pc,
 686                 void *pc)
 687 {
 688         int ret;
 689         unsigned long target_pc = pc - start_pc;
 690         struct cds_lfht_iter iter;
 691         struct cds_lfht_node *node;
 692         unsigned long hash;
 693
 694         /* Validate the context resulting from the previous instruction */
 695         ret = validate_instruction_context(bytecode, stack, start_pc, pc);
 696         if (ret)
 697                 return ret;
 698
 699         /* Validate merge points */
 700         hash = lttng_hash_mix((const void *) target_pc, sizeof(target_pc),
 701                         lttng_hash_seed);
 702         cds_lfht_for_each_duplicate(merge_points, hash, lttng_hash_match,
 703                         (const void *) target_pc, &iter, node) {
 704                 struct lfht_mp_node *mp_node =
 705                         caa_container_of(node, struct lfht_mp_node, node);
 706
 707                 dbg_printf("Filter: validate merge point at offset %lu\n",
 708                                 target_pc);
 709                 ret = validate_instruction_context(bytecode, &mp_node->stack,
 710                                 start_pc, pc);
 711                 if (ret)
 712                         return ret;
 713                 /* Once validated, we can remove the merge point */
 714                 dbg_printf("Filter: remove one merge point at offset %lu\n",
 715                                 target_pc);
 716                 ret = cds_lfht_del(merge_points, node);
 717                 assert(!ret);
 718         }
 719         return 0;
 720 }
 721
 722 /*
 723  * Return value:
 724  * >0: going to next insn.
 725  * 0: success, stop iteration.
 726  * <0: error
 727  */
 728 static
 729 int exec_insn(struct bytecode_runtime *bytecode,
 730                 struct cds_lfht *merge_points,
 731                 struct vstack *stack,
 732                 void **_next_pc,
 733                 void *pc)
 734 {
 735         int ret = 1;
 736         void *next_pc = *_next_pc;
 737
 738         switch (*(filter_opcode_t *) pc) {
 739         case FILTER_OP_UNKNOWN:
 740         default:
 741         {
 742                 ERR("unknown bytecode op %u\n",
 743                         (unsigned int) *(filter_opcode_t *) pc);
 744                 ret = -EINVAL;
 745                 goto end;
 746         }
 747
 748         case FILTER_OP_RETURN:
 749         {
 750                 ret = 0;
 751                 goto end;
 752         }
 753
 754         /* binary */
 755         case FILTER_OP_MUL:
 756         case FILTER_OP_DIV:
 757         case FILTER_OP_MOD:
 758         case FILTER_OP_PLUS:
 759         case FILTER_OP_MINUS:
 760         case FILTER_OP_RSHIFT:
 761         case FILTER_OP_LSHIFT:
 762         case FILTER_OP_BIN_AND:
 763         case FILTER_OP_BIN_OR:
 764         case FILTER_OP_BIN_XOR:
 765         {
 766                 ERR("unsupported bytecode op %u\n",
 767                         (unsigned int) *(filter_opcode_t *) pc);
 768                 ret = -EINVAL;
 769                 goto end;
 770         }
 771
 772         case FILTER_OP_EQ:
 773         case FILTER_OP_NE:
 774         case FILTER_OP_GT:
 775         case FILTER_OP_LT:
 776         case FILTER_OP_GE:
 777         case FILTER_OP_LE:
 778         case FILTER_OP_EQ_STRING:
 779         case FILTER_OP_NE_STRING:
 780         case FILTER_OP_GT_STRING:
 781         case FILTER_OP_LT_STRING:
 782         case FILTER_OP_GE_STRING:
 783         case FILTER_OP_LE_STRING:
 784         case FILTER_OP_EQ_S64:
 785         case FILTER_OP_NE_S64:
 786         case FILTER_OP_GT_S64:
 787         case FILTER_OP_LT_S64:
 788         case FILTER_OP_GE_S64:
 789         case FILTER_OP_LE_S64:
 790         case FILTER_OP_EQ_DOUBLE:
 791         case FILTER_OP_NE_DOUBLE:
 792         case FILTER_OP_GT_DOUBLE:
 793         case FILTER_OP_LT_DOUBLE:
 794         case FILTER_OP_GE_DOUBLE:
 795         case FILTER_OP_LE_DOUBLE:
 796         {
 797                 /* Pop 2, push 1 */
 798                 if (vstack_pop(stack)) {
 799                         ret = -EINVAL;
 800                         goto end;
 801                 }
 802                 if (!vstack_ax(stack)) {
 803                         ERR("Empty stack\n");
 804                         ret = -EINVAL;
 805                         goto end;
 806                 }
 807                 vstack_ax(stack)->type = REG_S64;
 808                 next_pc += sizeof(struct binary_op);
 809                 break;
 810         }
 811
 812         /* unary */
 813         case FILTER_OP_UNARY_PLUS:
 814         case FILTER_OP_UNARY_MINUS:
 815         case FILTER_OP_UNARY_NOT:
 816         case FILTER_OP_UNARY_PLUS_S64:
 817         case FILTER_OP_UNARY_MINUS_S64:
 818         case FILTER_OP_UNARY_NOT_S64:
 819         {
 820                 /* Pop 1, push 1 */
 821                 if (!vstack_ax(stack)) {
 822                         ERR("Empty stack\n");
 823                         ret = -EINVAL;
 824                         goto end;
 825                 }
 826                 vstack_ax(stack)->type = REG_S64;
 827                 next_pc += sizeof(struct unary_op);
 828                 break;
 829         }
 830
 831         case FILTER_OP_UNARY_PLUS_DOUBLE:
 832         case FILTER_OP_UNARY_MINUS_DOUBLE:
 833         case FILTER_OP_UNARY_NOT_DOUBLE:
 834         {
 835                 /* Pop 1, push 1 */
 836                 if (!vstack_ax(stack)) {
 837                         ERR("Empty stack\n");
 838                         ret = -EINVAL;
 839                         goto end;
 840                 }
 841                 vstack_ax(stack)->type = REG_DOUBLE;
 842                 next_pc += sizeof(struct unary_op);
 843                 break;
 844         }
 845
 846         /* logical */
 847         case FILTER_OP_AND:
 848         case FILTER_OP_OR:
 849         {
 850                 struct logical_op *insn = (struct logical_op *) pc;
 851                 int merge_ret;
 852
 853                 /* Add merge point to table */
 854                 merge_ret = merge_point_add(merge_points, insn->skip_offset,
 855                                         stack);
 856                 if (merge_ret) {
 857                         ret = merge_ret;
 858                         goto end;
 859                 }
 860                 /* Continue to next instruction */
 861                 next_pc += sizeof(struct logical_op);
 862                 break;
 863         }
 864
 865         /* load */
 866         case FILTER_OP_LOAD_FIELD_REF:
 867         {
 868                 ERR("Unknown field ref type\n");
 869                 ret = -EINVAL;
 870                 goto end;
 871         }
 872         case FILTER_OP_LOAD_FIELD_REF_STRING:
 873         case FILTER_OP_LOAD_FIELD_REF_SEQUENCE:
 874         {
 875                 if (vstack_push(stack)) {
 876                         ret = -EINVAL;
 877                         goto end;
 878                 }
 879                 vstack_ax(stack)->type = REG_STRING;
 880                 next_pc += sizeof(struct load_op) + sizeof(struct field_ref);
 881                 break;
 882         }
 883         case FILTER_OP_LOAD_FIELD_REF_S64:
 884         {
 885                 if (vstack_push(stack)) {
 886                         ret = -EINVAL;
 887                         goto end;
 888                 }
 889                 vstack_ax(stack)->type = REG_S64;
 890                 next_pc += sizeof(struct load_op) + sizeof(struct field_ref);
 891                 break;
 892         }
 893         case FILTER_OP_LOAD_FIELD_REF_DOUBLE:
 894         {
 895                 if (vstack_push(stack)) {
 896                         ret = -EINVAL;
 897                         goto end;
 898                 }
 899                 vstack_ax(stack)->type = REG_DOUBLE;
 900                 next_pc += sizeof(struct load_op) + sizeof(struct field_ref);
 901                 break;
 902         }
 903
 904         case FILTER_OP_LOAD_STRING:
 905         {
 906                 struct load_op *insn = (struct load_op *) pc;
 907
 908                 if (vstack_push(stack)) {
 909                         ret = -EINVAL;
 910                         goto end;
 911                 }
 912                 vstack_ax(stack)->type = REG_STRING;
 913                 next_pc += sizeof(struct load_op) + strlen(insn->data) + 1;
 914                 break;
 915         }
 916
 917         case FILTER_OP_LOAD_S64:
 918         {
 919                 if (vstack_push(stack)) {
 920                         ret = -EINVAL;
 921                         goto end;
 922                 }
 923                 vstack_ax(stack)->type = REG_S64;
 924                 next_pc += sizeof(struct load_op)
 925                                 + sizeof(struct literal_numeric);
 926                 break;
 927         }
 928
 929         case FILTER_OP_LOAD_DOUBLE:
 930         {
 931                 if (vstack_push(stack)) {
 932                         ret = -EINVAL;
 933                         goto end;
 934                 }
 935                 vstack_ax(stack)->type = REG_DOUBLE;
 936                 next_pc += sizeof(struct load_op)
 937                                 + sizeof(struct literal_double);
 938                 break;
 939         }
 940
 941         case FILTER_OP_CAST_TO_S64:
 942         case FILTER_OP_CAST_DOUBLE_TO_S64:
 943         {
 944                 /* Pop 1, push 1 */
 945                 if (!vstack_ax(stack)) {
 946                         ERR("Empty stack\n");
 947                         ret = -EINVAL;
 948                         goto end;
 949                 }
 950                 vstack_ax(stack)->type = REG_S64;
 951                 next_pc += sizeof(struct cast_op);
 952                 break;
 953         }
 954         case FILTER_OP_CAST_NOP:
 955         {
 956                 next_pc += sizeof(struct cast_op);
 957                 break;
 958         }
 959
 960         }
 961 end:
 962         *_next_pc = next_pc;
 963         return ret;
 964 }
 965
 966 /*
 967  * Never called concurrently (hash seed is shared).
 968  */
 969 int lttng_filter_validate_bytecode(struct bytecode_runtime *bytecode)
 970 {
 971         struct cds_lfht *merge_points;
 972         void *pc, *next_pc, *start_pc;
 973         int ret = -EINVAL;
 974         struct vstack stack;
 975
 976         vstack_init(&stack);
 977
 978         if (!lttng_hash_seed_ready) {
 979                 lttng_hash_seed = time(NULL);
 980                 lttng_hash_seed_ready = 1;
 981         }
 982         /*
 983          * Note: merge_points hash table used by single thread, and
 984          * never concurrently resized. Therefore, we can use it without
 985          * holding RCU read-side lock and free nodes without using
 986          * call_rcu.
 987          */
 988         merge_points = cds_lfht_new(DEFAULT_NR_MERGE_POINTS,
 989                         MIN_NR_BUCKETS, MAX_NR_BUCKETS,
 990                         0, NULL);
 991         if (!merge_points) {
 992                 ERR("Error allocating hash table for bytecode validation\n");
 993                 return -ENOMEM;
 994         }
 995         start_pc = &bytecode->data[0];
 996         for (pc = next_pc = start_pc; pc - start_pc < bytecode->len;
 997                         pc = next_pc) {
 998                 if (bytecode_validate_overflow(bytecode, start_pc, pc) != 0) {
 999                         ERR("filter bytecode overflow\n");
1000                         ret = -EINVAL;
1001                         goto end;
1002                 }
1003                 dbg_printf("Validating op %s (%u)\n",
1004                         print_op((unsigned int) *(filter_opcode_t *) pc),
1005                         (unsigned int) *(filter_opcode_t *) pc);
1006
1007                 /*
1008                  * For each instruction, validate the current context
1009                  * (traversal of entire execution flow), and validate
1010                  * all  merge points targeting this instruction.
1011                  */
1012                 ret = validate_instruction_all_contexts(bytecode, merge_points,
1013                                         &stack, start_pc, pc);
1014                 if (ret)
1015                         goto end;
1016                 ret = exec_insn(bytecode, merge_points, &stack, &next_pc, pc);
1017                 if (ret <= 0)
1018                         goto end;
1019         }
1020 end:
1021         if (delete_all_nodes(merge_points)) {
1022                 if (!ret) {
1023                         ERR("Unexpected merge points\n");
1024                         ret = -EINVAL;
1025                 }
1026         }
1027         if (cds_lfht_destroy(merge_points, NULL)) {
1028                 ERR("Error destroying hash table\n");
1029         }
1030         return ret;
1031 }