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