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