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