epan/dfilter/gencode.c

   1 /*
   2  * Wireshark - Network traffic analyzer
   3  * By Gerald Combs <gerald@wireshark.org>
   4  * Copyright 2001 Gerald Combs
   5  *
   6  * SPDX-License-Identifier: GPL-2.0-or-later
   7  */
   8
   9 #include "config.h"
  10
  11 #include "gencode.h"
  12 #include "dfvm.h"
  13 #include "syntax-tree.h"
  14 #include "sttype-field.h"
  15 #include "sttype-slice.h"
  16 #include "sttype-op.h"
  17 #include "sttype-set.h"
  18 #include "sttype-function.h"
  19 #include "ftypes/ftypes.h"
  20 #include <wsutil/ws_assert.h>
  21
  22 static void
  23 fixup_jumps(void *data, void *user_data);
  24
  25 static dfvm_value_t *
  26 gencode(dfwork_t *dfw, stnode_t *st_node);
  27
  28 static dfvm_value_t *
  29 gen_entity(dfwork_t *dfw, stnode_t *st_arg, GSList **jumps_ptr);
  30
  31 static dfvm_opcode_t
  32 select_opcode(dfvm_opcode_t op, stmatch_t how)
  33 {
  34         if (how == STNODE_MATCH_DEF)
  35                 return op;
  36
  37         switch (op) {
  38                 case DFVM_ALL_EQ:
  39                 case DFVM_ALL_NE:
  40                 case DFVM_ALL_GT:
  41                 case DFVM_ALL_GE:
  42                 case DFVM_ALL_LT:
  43                 case DFVM_ALL_LE:
  44                 case DFVM_ALL_CONTAINS:
  45                 case DFVM_ALL_MATCHES:
  46                 case DFVM_SET_ALL_IN:
  47                 case DFVM_SET_ALL_NOT_IN:
  48                         return how == STNODE_MATCH_ALL ? op : op + 1;
  49                 case DFVM_ANY_EQ:
  50                 case DFVM_ANY_NE:
  51                 case DFVM_ANY_GT:
  52                 case DFVM_ANY_GE:
  53                 case DFVM_ANY_LT:
  54                 case DFVM_ANY_LE:
  55                 case DFVM_ANY_CONTAINS:
  56                 case DFVM_ANY_MATCHES:
  57                 case DFVM_SET_ANY_IN:
  58                 case DFVM_SET_ANY_NOT_IN:
  59                         return how == STNODE_MATCH_ANY ? op : op - 1;
  60                 default:
  61                         ASSERT_DFVM_OP_NOT_REACHED(op);
  62         }
  63         ws_assert_not_reached();
  64 }
  65
  66 static void
  67 dfw_append_insn(dfwork_t *dfw, dfvm_insn_t *insn)
  68 {
  69         insn->id = dfw->next_insn_id;
  70         dfw->next_insn_id++;
  71         g_ptr_array_add(dfw->insns, insn);
  72 }
  73
  74 static void
  75 dfw_append_stack_push(dfwork_t *dfw, dfvm_value_t *arg1)
  76 {
  77         dfvm_insn_t     *insn;
  78
  79         insn = dfvm_insn_new(DFVM_STACK_PUSH);
  80         insn->arg1 = dfvm_value_ref(arg1);
  81         dfw_append_insn(dfw, insn);
  82 }
  83
  84 static void
  85 dfw_append_stack_pop(dfwork_t *dfw, unsigned count)
  86 {
  87         dfvm_insn_t     *insn;
  88         dfvm_value_t    *val;
  89
  90         insn = dfvm_insn_new(DFVM_STACK_POP);
  91         val = dfvm_value_new_uint(count);
  92         insn->arg1 = dfvm_value_ref(val);
  93         dfw_append_insn(dfw, insn);
  94 }
  95
  96 static void
  97 dfw_append_set_add_range(dfwork_t *dfw, dfvm_value_t *arg1, dfvm_value_t *arg2)
  98 {
  99         dfvm_insn_t     *insn;
 100
 101         insn = dfvm_insn_new(DFVM_SET_ADD_RANGE);
 102         insn->arg1 = dfvm_value_ref(arg1);
 103         insn->arg2 = dfvm_value_ref(arg2);
 104         dfw_append_insn(dfw, insn);
 105 }
 106
 107 static void
 108 dfw_append_set_add(dfwork_t *dfw, dfvm_value_t *arg1)
 109 {
 110         dfvm_insn_t     *insn;
 111
 112         insn = dfvm_insn_new(DFVM_SET_ADD);
 113         insn->arg1 = dfvm_value_ref(arg1);
 114         dfw_append_insn(dfw, insn);
 115 }
 116
 117 static dfvm_value_t *
 118 dfw_append_jump(dfwork_t *dfw)
 119 {
 120         dfvm_insn_t     *insn;
 121         dfvm_value_t    *jmp;
 122
 123         insn = dfvm_insn_new(DFVM_IF_FALSE_GOTO);
 124         jmp = dfvm_value_new(INSN_NUMBER);
 125         insn->arg1 = dfvm_value_ref(jmp);
 126         dfw_append_insn(dfw, insn);
 127         return jmp;
 128 }
 129
 130 /* returns register number */
 131 static dfvm_value_t *
 132 dfw_append_read_tree(dfwork_t *dfw, header_field_info *hfinfo,
 133                                                 drange_t *range,
 134                                                 bool raw)
 135 {
 136         dfvm_insn_t     *insn;
 137         int             reg = -1;
 138         dfvm_value_t    *reg_val, *val1, *val3;
 139         bool    added_new_hfinfo = false;
 140         GHashTable *loaded_fields;
 141         void *loaded_key;
 142
 143         /* Rewind to find the first field of this name. */
 144         while (hfinfo->same_name_prev_id != -1) {
 145                 hfinfo = proto_registrar_get_nth(hfinfo->same_name_prev_id);
 146         }
 147
 148         if (raw)
 149                 loaded_fields = dfw->loaded_raw_fields;
 150         else
 151                 loaded_fields = dfw->loaded_fields;
 152
 153         /* Keep track of which registers
 154          * were used for which hfinfo's so that we
 155          * can re-use registers. */
 156         /* Re-use only if we are not using a range (layer filter). */
 157         loaded_key = g_hash_table_lookup(loaded_fields, hfinfo);
 158         if (loaded_key != NULL) {
 159                 if (range == NULL) {
 160                         /*
 161                          * Reg's are stored in has as reg+1, so
 162                          * that the non-existence of a hfinfo in
 163                          * the hash, or 0, can be differentiated from
 164                          * a hfinfo being loaded into register #0.
 165                          */
 166                         reg = GPOINTER_TO_INT(loaded_key) - 1;
 167                 }
 168                 else {
 169                         reg = dfw->next_register++;
 170                 }
 171         }
 172         else {
 173                 reg = dfw->next_register++;
 174                 g_hash_table_insert(loaded_fields,
 175                         hfinfo, GINT_TO_POINTER(reg + 1));
 176
 177                 added_new_hfinfo = true;
 178         }
 179
 180         val1 = dfvm_value_new_hfinfo(hfinfo, raw);
 181         reg_val = dfvm_value_new_register(reg);
 182         if (range) {
 183                 val3 = dfvm_value_new_drange(range);
 184                 insn = dfvm_insn_new(DFVM_READ_TREE_R);
 185         }
 186         else {
 187                 val3 = NULL;
 188                 insn = dfvm_insn_new(DFVM_READ_TREE);
 189         }
 190         insn->arg1 = dfvm_value_ref(val1);
 191         insn->arg2 = dfvm_value_ref(reg_val);
 192         insn->arg3 = dfvm_value_ref(val3);
 193         dfw_append_insn(dfw, insn);
 194
 195         if (added_new_hfinfo) {
 196                 while (hfinfo) {
 197                         /* Record the FIELD_ID in hash of interesting fields. */
 198                         g_hash_table_add(dfw->interesting_fields, &hfinfo->id);
 199                         hfinfo = hfinfo->same_name_next;
 200                 }
 201         }
 202
 203         return reg_val;
 204 }
 205
 206 /* returns register number */
 207 static dfvm_value_t *
 208 dfw_append_read_reference(dfwork_t *dfw, header_field_info *hfinfo,
 209                                                 drange_t *range,
 210                                                 bool raw)
 211 {
 212         dfvm_insn_t     *insn;
 213         dfvm_value_t    *reg_val, *val1, *val3;
 214         GPtrArray       *refs_array;
 215
 216         /* Rewind to find the first field of this name. */
 217         while (hfinfo->same_name_prev_id != -1) {
 218                 hfinfo = proto_registrar_get_nth(hfinfo->same_name_prev_id);
 219         }
 220
 221         /* We can't reuse registers with a filter so just skip
 222          * that optimization and don't reuse them at all. */
 223         val1 = dfvm_value_new_hfinfo(hfinfo, raw);
 224         reg_val = dfvm_value_new_register(dfw->next_register++);
 225         if (range) {
 226                 val3 = dfvm_value_new_drange(range);
 227                 insn = dfvm_insn_new(DFVM_READ_REFERENCE_R);
 228         }
 229         else {
 230                 val3 = NULL;
 231                 insn = dfvm_insn_new(DFVM_READ_REFERENCE);
 232         }
 233         insn->arg1 = dfvm_value_ref(val1);
 234         insn->arg2 = dfvm_value_ref(reg_val);
 235         insn->arg3 = dfvm_value_ref(val3);
 236         dfw_append_insn(dfw, insn);
 237
 238         refs_array = g_ptr_array_new_with_free_func((GDestroyNotify)reference_free);
 239         if (raw)
 240                 g_hash_table_insert(dfw->raw_references, hfinfo, refs_array);
 241         else
 242                 g_hash_table_insert(dfw->references, hfinfo, refs_array);
 243
 244         /* Record the FIELD_ID in hash of interesting fields. */
 245         while (hfinfo) {
 246                 /* Record the FIELD_ID in hash of interesting fields. */
 247                 g_hash_table_add(dfw->interesting_fields, &hfinfo->id);
 248                 hfinfo = hfinfo->same_name_next;
 249         }
 250
 251         return reg_val;
 252 }
 253
 254 /* returns register number */
 255 static dfvm_value_t *
 256 dfw_append_mk_slice(dfwork_t *dfw, stnode_t *node, GSList **jumps_ptr)
 257 {
 258         stnode_t                *entity;
 259         dfvm_insn_t             *insn;
 260         dfvm_value_t            *reg_val, *val1, *val3;
 261
 262         entity = sttype_slice_entity(node);
 263
 264         insn = dfvm_insn_new(DFVM_SLICE);
 265         val1 = gen_entity(dfw, entity, jumps_ptr);
 266         insn->arg1 = dfvm_value_ref(val1);
 267         reg_val = dfvm_value_new_register(dfw->next_register++);
 268         insn->arg2 = dfvm_value_ref(reg_val);
 269         val3 = dfvm_value_new_drange(sttype_slice_drange_steal(node));
 270         insn->arg3 = dfvm_value_ref(val3);
 271         sttype_slice_remove_drange(node);
 272         dfw_append_insn(dfw, insn);
 273
 274         return reg_val;
 275 }
 276
 277 /* Returns register number. This applies the value string in hfinfo to the
 278  * contents of the src register. */
 279 static dfvm_value_t *
 280 dfw_append_mk_value_string(dfwork_t *dfw, stnode_t *node, dfvm_value_t *src)
 281 {
 282         dfvm_insn_t             *insn;
 283         dfvm_value_t            *reg_val, *val1;
 284
 285         insn = dfvm_insn_new(DFVM_VALUE_STRING);
 286         val1 = dfvm_value_new_hfinfo(sttype_field_hfinfo(node), false);
 287         insn->arg1 = dfvm_value_ref(val1);
 288         insn->arg2 = dfvm_value_ref(src);
 289         reg_val = dfvm_value_new_register(dfw->next_register++);
 290         insn->arg3 = dfvm_value_ref(reg_val);
 291         dfw_append_insn(dfw, insn);
 292
 293         return reg_val;
 294 }
 295
 296 /* returns register number */
 297 _U_ static dfvm_value_t *
 298 dfw_append_put_fvalue(dfwork_t *dfw, fvalue_t *fv)
 299 {
 300         dfvm_insn_t             *insn;
 301         dfvm_value_t            *reg_val, *val1;
 302
 303         insn = dfvm_insn_new(DFVM_PUT_FVALUE);
 304         val1 = dfvm_value_new_fvalue(fv);
 305         insn->arg1 = dfvm_value_ref(val1);
 306         reg_val = dfvm_value_new_register(dfw->next_register++);
 307         insn->arg2 = dfvm_value_ref(reg_val);
 308         dfw_append_insn(dfw, insn);
 309
 310         return reg_val;
 311 }
 312
 313 /* returns register number that the length's result will be in. */
 314 static dfvm_value_t *
 315 dfw_append_length(dfwork_t *dfw, stnode_t *node, GSList **jumps_ptr)
 316 {
 317         GSList *params;
 318         dfvm_insn_t     *insn;
 319         dfvm_value_t    *reg_val, *val_arg;
 320
 321         /* Create the new DFVM instruction */
 322         insn = dfvm_insn_new(DFVM_LENGTH);
 323         /* Create input argument */
 324         params = sttype_function_params(node);
 325         ws_assert(params);
 326         ws_assert(g_slist_length(params) == 1);
 327         val_arg = gen_entity(dfw, params->data, jumps_ptr);
 328         insn->arg1 = dfvm_value_ref(val_arg);
 329         /* Destination. */
 330         reg_val = dfvm_value_new_register(dfw->next_register++);
 331         insn->arg2 = dfvm_value_ref(reg_val);
 332
 333         dfw_append_insn(dfw, insn);
 334         return reg_val;
 335 }
 336
 337 /* returns register number that the value string result will be in. */
 338 static dfvm_value_t *
 339 dfw_append_value_string(dfwork_t *dfw, stnode_t *node, GSList **jumps_ptr)
 340 {
 341         GSList *params;
 342
 343         params = sttype_function_params(node);
 344         ws_assert(params);
 345         ws_assert(g_slist_length(params) == 1);
 346         return gen_entity(dfw, params->data, jumps_ptr);
 347 }
 348
 349 /* returns register number that the functions's result will be in. */
 350 static dfvm_value_t *
 351 dfw_append_function(dfwork_t *dfw, stnode_t *node, GSList **jumps_ptr)
 352 {
 353         GSList          *params;
 354         dfvm_value_t    *jmp;
 355         dfvm_insn_t     *insn;
 356         dfvm_value_t    *reg_val, *val1, *val3, *val_arg;
 357         unsigned        count;
 358         df_func_def_t   *func;
 359         GSList          *params_jumps = NULL;
 360
 361         func = sttype_function_funcdef(node);
 362
 363         if (strcmp(func->name, "len") == 0) {
 364                 /* Replace len() function call with DFVM_LENGTH instruction. */
 365                 return dfw_append_length(dfw, node, jumps_ptr);
 366         }
 367
 368         if (strcmp(func->name, "vals") == 0) {
 369                 /* Replace vals() function call with DFVM_VALUE_STRING instruction. */
 370                 return dfw_append_value_string(dfw, node, jumps_ptr);
 371         }
 372
 373         /* Create the new DFVM instruction */
 374         insn = dfvm_insn_new(DFVM_CALL_FUNCTION);
 375         val1 = dfvm_value_new_funcdef(func);
 376         insn->arg1 = dfvm_value_ref(val1);
 377         reg_val = dfvm_value_new_register(dfw->next_register++);
 378         insn->arg2 = dfvm_value_ref(reg_val);
 379
 380         /* Create input arguments */
 381         params = sttype_function_params(node);
 382         ws_assert(params);
 383         count = 0;
 384         while (params) {
 385                 val_arg = gen_entity(dfw, params->data, &params_jumps);
 386                 /* If a parameter fails to generate jump here.
 387                  * Note: stack_push NULL register is valid. */
 388                 g_slist_foreach(params_jumps, fixup_jumps, dfw);
 389                 g_slist_free(params_jumps);
 390                 params_jumps = NULL;
 391                 dfw_append_stack_push(dfw, val_arg);
 392                 count++;
 393                 params = params->next;
 394         }
 395         val3 = dfvm_value_new_uint(count);
 396         insn->arg3 = dfvm_value_ref(val3);
 397         dfw_append_insn(dfw, insn);
 398         dfw_append_stack_pop(dfw, count);
 399
 400         /* We need another instruction to jump to another exit
 401          * place, if the call() of our function failed for some reason */
 402         insn = dfvm_insn_new(DFVM_IF_FALSE_GOTO);
 403         jmp = dfvm_value_new(INSN_NUMBER);
 404         insn->arg1 = dfvm_value_ref(jmp);
 405         dfw_append_insn(dfw, insn);
 406         *jumps_ptr = g_slist_prepend(*jumps_ptr, jmp);
 407
 408         return reg_val;
 409 }
 410
 411 /**
 412  * Adds an instruction for a relation operator where the values are already
 413  * loaded in registers.
 414  */
 415 static void
 416 gen_relation_insn(dfwork_t *dfw, dfvm_opcode_t op,
 417                         dfvm_value_t *arg1, dfvm_value_t *arg2,
 418                         dfvm_value_t *arg3)
 419 {
 420         dfvm_insn_t     *insn;
 421
 422         insn = dfvm_insn_new(op);
 423         insn->arg1 = dfvm_value_ref(arg1);
 424         insn->arg2 = dfvm_value_ref(arg2);
 425         insn->arg3 = dfvm_value_ref(arg3);
 426         dfw_append_insn(dfw, insn);
 427 }
 428
 429 static void
 430 gen_relation(dfwork_t *dfw, dfvm_opcode_t op, stmatch_t how,
 431                                         stnode_t *st_arg1, stnode_t *st_arg2)
 432 {
 433         GSList          *jumps = NULL;
 434         dfvm_value_t    *val1, *val2;
 435
 436         /* Create code for the LHS and RHS of the relation */
 437         val1 = gen_entity(dfw, st_arg1, &jumps);
 438         val2 = gen_entity(dfw, st_arg2, &jumps);
 439
 440         /* Then combine them in a DFVM instruction */
 441         op = select_opcode(op, how);
 442         gen_relation_insn(dfw, op, val1, val2, NULL);
 443
 444         /* If either of the relation arguments need an "exit" instruction
 445          * to jump to (on failure), mark them */
 446         g_slist_foreach(jumps, fixup_jumps, dfw);
 447         g_slist_free(jumps);
 448         jumps = NULL;
 449 }
 450
 451 static void
 452 fixup_jumps(void *data, void *user_data)
 453 {
 454         dfvm_value_t *jmp = (dfvm_value_t*)data;
 455         dfwork_t *dfw = (dfwork_t*)user_data;
 456
 457         if (jmp) {
 458                 jmp->value.numeric = dfw->next_insn_id;
 459         }
 460 }
 461
 462 /* Generate the code for the in operator. Pushes set values into a stack
 463  * and then evaluates membership in a single instruction. */
 464 static void
 465 gen_relation_in(dfwork_t *dfw, dfvm_opcode_t op, stmatch_t how,
 466                                 stnode_t *st_arg1, stnode_t *st_arg2)
 467 {
 468         dfvm_insn_t     *insn;
 469         GSList          *jumps = NULL;
 470         GSList          *node_jumps = NULL;
 471         dfvm_value_t    *val1, *val2, *val3;
 472         stnode_t        *node1, *node2;
 473         GSList          *nodelist_head, *nodelist;
 474
 475         /* Create code for the LHS of the relation */
 476         val1 = gen_entity(dfw, st_arg1, &jumps);
 477
 478         /* Create code to populate the set stack */
 479         nodelist_head = nodelist = stnode_steal_data(st_arg2);
 480         while (nodelist) {
 481                 node1 = nodelist->data;
 482                 nodelist = g_slist_next(nodelist);
 483                 node2 = nodelist->data;
 484                 nodelist = g_slist_next(nodelist);
 485
 486                 if (node2) {
 487                         /* Range element. */
 488                         val2 = gen_entity(dfw, node1, &node_jumps);
 489                         val3 = gen_entity(dfw, node2, &node_jumps);
 490                         dfw_append_set_add_range(dfw, val2, val3);
 491                 } else {
 492                         /* Normal element. */
 493                         val2 = gen_entity(dfw, node1, &node_jumps);
 494                         dfw_append_set_add(dfw, val2);
 495                 }
 496
 497                 /* If an item is not present, just jump to the next item */
 498                 g_slist_foreach(node_jumps, fixup_jumps, dfw);
 499                 g_slist_free(node_jumps);
 500                 node_jumps = NULL;
 501         }
 502         set_nodelist_free(nodelist_head);
 503
 504         /* Create code for the set on the RHS of the relation */
 505         insn = dfvm_insn_new(select_opcode(op, how));
 506         insn->arg1 = dfvm_value_ref(val1);
 507         dfw_append_insn(dfw, insn);
 508
 509         /* Add instruction to clear the whole stack */
 510         insn = dfvm_insn_new(DFVM_SET_CLEAR);
 511         dfw_append_insn(dfw, insn);
 512
 513         /* Jump here if the LHS entity was not present */
 514         g_slist_foreach(jumps, fixup_jumps, dfw);
 515         g_slist_free(jumps);
 516         jumps = NULL;
 517 }
 518
 519 static dfvm_value_t *
 520 gen_arithmetic(dfwork_t *dfw, stnode_t *st_arg, GSList **jumps_ptr)
 521 {
 522         stnode_t        *left, *right;
 523         stnode_op_t     st_op;
 524         dfvm_value_t    *reg_val, *val1, *val2 = NULL;
 525         dfvm_opcode_t   op = DFVM_NULL;
 526
 527         sttype_oper_get(st_arg, &st_op, &left, &right);
 528
 529         switch (st_op) {
 530                 case STNODE_OP_UNARY_MINUS:     op = DFVM_UNARY_MINUS; break;
 531                 case STNODE_OP_ADD:             op = DFVM_ADD; break;
 532                 case STNODE_OP_SUBTRACT:        op = DFVM_SUBTRACT; break;
 533                 case STNODE_OP_MULTIPLY:        op = DFVM_MULTIPLY; break;
 534                 case STNODE_OP_DIVIDE:          op = DFVM_DIVIDE; break;
 535                 case STNODE_OP_MODULO:          op = DFVM_MODULO; break;
 536                 case STNODE_OP_BITWISE_AND:     op = DFVM_BITWISE_AND; break;
 537
 538                 /* fall-through */
 539                 case STNODE_OP_NOT:
 540                 case STNODE_OP_AND:
 541                 case STNODE_OP_OR:
 542                 case STNODE_OP_ALL_EQ:
 543                 case STNODE_OP_ANY_EQ:
 544                 case STNODE_OP_ALL_NE:
 545                 case STNODE_OP_ANY_NE:
 546                 case STNODE_OP_GT:
 547                 case STNODE_OP_GE:
 548                 case STNODE_OP_LT:
 549                 case STNODE_OP_LE:
 550                 case STNODE_OP_CONTAINS:
 551                 case STNODE_OP_MATCHES:
 552                 case STNODE_OP_IN:
 553                 case STNODE_OP_NOT_IN:
 554                 case STNODE_OP_UNINITIALIZED:
 555                         ASSERT_STNODE_OP_NOT_REACHED(st_op);
 556         }
 557
 558         val1 = gen_entity(dfw, left, jumps_ptr);
 559         if (right == NULL) {
 560                 /* Generate unary DFVM instruction. */
 561                 reg_val = dfvm_value_new_register(dfw->next_register++);
 562                 gen_relation_insn(dfw, op, val1, reg_val, NULL);
 563                 return reg_val;
 564         }
 565
 566         val2 = gen_entity(dfw, right, jumps_ptr);
 567         reg_val = dfvm_value_new_register(dfw->next_register++);
 568         gen_relation_insn(dfw, op, val1, val2, reg_val);
 569         return reg_val;
 570 }
 571
 572 /* Parse an entity, returning the reg that it gets put into.
 573  * p_jmp will be set if it has to be set by the calling code; it should
 574  * be set to the place to jump to, to return to the calling code,
 575  * if the load of a field from the proto_tree fails. */
 576 static dfvm_value_t *
 577 gen_entity(dfwork_t *dfw, stnode_t *st_arg, GSList **jumps_ptr)
 578 {
 579         sttype_id_t       e_type;
 580         dfvm_value_t      *val;
 581         header_field_info *hfinfo;
 582         drange_t *range = NULL;
 583         bool raw;
 584         e_type = stnode_type_id(st_arg);
 585
 586         if (e_type == STTYPE_FIELD) {
 587                 hfinfo = sttype_field_hfinfo(st_arg);
 588                 range = sttype_field_drange_steal(st_arg);
 589                 raw = sttype_field_raw(st_arg);
 590                 val = dfw_append_read_tree(dfw, hfinfo, range, raw);
 591                 if (jumps_ptr != NULL) {
 592                         *jumps_ptr = g_slist_prepend(*jumps_ptr, dfw_append_jump(dfw));
 593                 }
 594                 if (sttype_field_value_string(st_arg)) {
 595                         val = dfw_append_mk_value_string(dfw, st_arg, val);
 596                         if (jumps_ptr != NULL) {
 597                                 *jumps_ptr = g_slist_prepend(*jumps_ptr, dfw_append_jump(dfw));
 598                         }
 599                 }
 600         }
 601         else if (e_type == STTYPE_REFERENCE) {
 602                 hfinfo = sttype_field_hfinfo(st_arg);
 603                 range = sttype_field_drange_steal(st_arg);
 604                 raw = sttype_field_raw(st_arg);
 605                 val = dfw_append_read_reference(dfw, hfinfo, range, raw);
 606                 if (jumps_ptr != NULL) {
 607                         *jumps_ptr = g_slist_prepend(*jumps_ptr, dfw_append_jump(dfw));
 608                 }
 609                 if (sttype_field_value_string(st_arg)) {
 610                         val = dfw_append_mk_value_string(dfw, st_arg, val);
 611                         if (jumps_ptr != NULL) {
 612                                 *jumps_ptr = g_slist_prepend(*jumps_ptr, dfw_append_jump(dfw));
 613                         }
 614                 }
 615         }
 616         else if (e_type == STTYPE_FVALUE) {
 617                 val = dfvm_value_new_fvalue(stnode_steal_data(st_arg));
 618         }
 619         else if (e_type == STTYPE_SLICE) {
 620                 val = dfw_append_mk_slice(dfw, st_arg, jumps_ptr);
 621         }
 622         else if (e_type == STTYPE_FUNCTION) {
 623                 val = dfw_append_function(dfw, st_arg, jumps_ptr);
 624         }
 625         else if (e_type == STTYPE_PCRE) {
 626                 val = dfvm_value_new_pcre(stnode_steal_data(st_arg));
 627         }
 628         else if (e_type == STTYPE_ARITHMETIC) {
 629                 val = gen_arithmetic(dfw, st_arg, jumps_ptr);
 630         }
 631         else {
 632                 ws_error("Invalid sttype: %s", stnode_type_name(st_arg));
 633         }
 634         return val;
 635 }
 636
 637 static void
 638 gen_exists(dfwork_t *dfw, stnode_t *st_node)
 639 {
 640         dfvm_insn_t *insn;
 641         dfvm_value_t *val1, *val2 = NULL;
 642         header_field_info *hfinfo;
 643         drange_t *range = NULL;
 644
 645         hfinfo = sttype_field_hfinfo(st_node);
 646         range = sttype_field_drange_steal(st_node);
 647
 648         /* Rewind to find the first field of this name. */
 649         while (hfinfo->same_name_prev_id != -1) {
 650                 hfinfo = proto_registrar_get_nth(hfinfo->same_name_prev_id);
 651         }
 652
 653         /* Ignore "rawness" for existence tests. */
 654         val1 = dfvm_value_new_hfinfo(hfinfo, false);
 655         if (range) {
 656                 val2 = dfvm_value_new_drange(range);
 657         }
 658
 659         if (val2) {
 660                 insn = dfvm_insn_new(DFVM_CHECK_EXISTS_R);
 661                 insn->arg1 = dfvm_value_ref(val1);
 662                 insn->arg2 = dfvm_value_ref(val2);
 663         }
 664         else {
 665                 insn = dfvm_insn_new(DFVM_CHECK_EXISTS);
 666                 insn->arg1 = dfvm_value_ref(val1);
 667         }
 668         dfw_append_insn(dfw, insn);
 669
 670         /* Record the FIELD_ID in hash of interesting fields. */
 671         while (hfinfo) {
 672                 g_hash_table_add(dfw->interesting_fields, &hfinfo->id);
 673                 hfinfo = hfinfo->same_name_next;
 674         }
 675 }
 676
 677 static dfvm_value_t*
 678 gen_field(dfwork_t *dfw, stnode_t *st_node)
 679 {
 680         dfvm_value_t    *val1;
 681         GSList          *jumps = NULL;
 682
 683         val1 = gen_entity(dfw, st_node, &jumps);
 684         g_slist_foreach(jumps, fixup_jumps, dfw);
 685         g_slist_free(jumps);
 686         return val1;
 687 }
 688
 689 static dfvm_value_t*
 690 gen_notzero(dfwork_t *dfw, stnode_t *st_node)
 691 {
 692         dfvm_insn_t     *insn;
 693         dfvm_value_t    *val1;
 694         GSList          *jumps = NULL;
 695
 696         val1 = gen_entity(dfw, st_node, &jumps);
 697         insn = dfvm_insn_new(DFVM_NOT_ALL_ZERO);
 698         insn->arg1 = dfvm_value_ref(val1);
 699         dfw_append_insn(dfw, insn);
 700         g_slist_foreach(jumps, fixup_jumps, dfw);
 701         g_slist_free(jumps);
 702         return val1;
 703 }
 704
 705 static dfvm_value_t*
 706 gen_notzero_slice(dfwork_t *dfw, stnode_t *st_node)
 707 {
 708         dfvm_insn_t     *insn;
 709         dfvm_value_t    *val1, *reg_val;
 710         GSList          *jumps = NULL;
 711
 712         val1 = gen_entity(dfw, st_node, &jumps);
 713         /* Compute length. */
 714         insn = dfvm_insn_new(DFVM_LENGTH);
 715         insn->arg1 = dfvm_value_ref(val1);
 716         reg_val = dfvm_value_new_register(dfw->next_register++);
 717         insn->arg2 = dfvm_value_ref(reg_val);
 718         dfw_append_insn(dfw, insn);
 719         /* Check length is not zero. */
 720         insn = dfvm_insn_new(DFVM_NOT_ALL_ZERO);
 721         insn->arg1 = dfvm_value_ref(reg_val);
 722         dfw_append_insn(dfw, insn);
 723         /* Fixup jumps. */
 724         g_slist_foreach(jumps, fixup_jumps, dfw);
 725         g_slist_free(jumps);
 726         return val1;
 727 }
 728
 729 static void
 730 gen_test(dfwork_t *dfw, stnode_t *st_node)
 731 {
 732         stnode_op_t     st_op;
 733         stmatch_t       st_how;
 734         stnode_t        *st_arg1, *st_arg2;
 735         dfvm_insn_t     *insn;
 736         dfvm_value_t    *jmp;
 737
 738
 739         sttype_oper_get(st_node, &st_op, &st_arg1, &st_arg2);
 740         st_how = sttype_test_get_match(st_node);
 741
 742         switch (st_op) {
 743                 case STNODE_OP_NOT:
 744                         gencode(dfw, st_arg1);
 745                         insn = dfvm_insn_new(DFVM_NOT);
 746                         dfw_append_insn(dfw, insn);
 747                         break;
 748
 749                 case STNODE_OP_AND:
 750                         gencode(dfw, st_arg1);
 751
 752                         insn = dfvm_insn_new(DFVM_IF_FALSE_GOTO);
 753                         jmp = dfvm_value_new(INSN_NUMBER);
 754                         insn->arg1 = dfvm_value_ref(jmp);
 755                         dfw_append_insn(dfw, insn);
 756
 757                         gencode(dfw, st_arg2);
 758                         jmp->value.numeric = dfw->next_insn_id;
 759                         break;
 760
 761                 case STNODE_OP_OR:
 762                         gencode(dfw, st_arg1);
 763
 764                         insn = dfvm_insn_new(DFVM_IF_TRUE_GOTO);
 765                         jmp = dfvm_value_new(INSN_NUMBER);
 766                         insn->arg1 = dfvm_value_ref(jmp);
 767                         dfw_append_insn(dfw, insn);
 768
 769                         gencode(dfw, st_arg2);
 770                         jmp->value.numeric = dfw->next_insn_id;
 771                         break;
 772
 773                 case STNODE_OP_ALL_EQ:
 774                         gen_relation(dfw, DFVM_ALL_EQ, st_how, st_arg1, st_arg2);
 775                         break;
 776
 777                 case STNODE_OP_ANY_EQ:
 778                         gen_relation(dfw, DFVM_ANY_EQ, st_how, st_arg1, st_arg2);
 779                         break;
 780
 781                 case STNODE_OP_ALL_NE:
 782                         gen_relation(dfw, DFVM_ALL_NE, st_how, st_arg1, st_arg2);
 783                         break;
 784
 785                 case STNODE_OP_ANY_NE:
 786                         gen_relation(dfw, DFVM_ANY_NE, st_how, st_arg1, st_arg2);
 787                         break;
 788
 789                 case STNODE_OP_GT:
 790                         gen_relation(dfw, DFVM_ANY_GT, st_how, st_arg1, st_arg2);
 791                         break;
 792
 793                 case STNODE_OP_GE:
 794                         gen_relation(dfw, DFVM_ANY_GE, st_how, st_arg1, st_arg2);
 795                         break;
 796
 797                 case STNODE_OP_LT:
 798                         gen_relation(dfw, DFVM_ANY_LT, st_how, st_arg1, st_arg2);
 799                         break;
 800
 801                 case STNODE_OP_LE:
 802                         gen_relation(dfw, DFVM_ANY_LE, st_how, st_arg1, st_arg2);
 803                         break;
 804
 805                 case STNODE_OP_CONTAINS:
 806                         gen_relation(dfw, DFVM_ANY_CONTAINS, st_how, st_arg1, st_arg2);
 807                         break;
 808
 809                 case STNODE_OP_MATCHES:
 810                         gen_relation(dfw, DFVM_ANY_MATCHES, st_how, st_arg1, st_arg2);
 811                         break;
 812
 813                 case STNODE_OP_IN:
 814                         gen_relation_in(dfw, DFVM_SET_ANY_IN, st_how, st_arg1, st_arg2);
 815                         break;
 816
 817                 case STNODE_OP_NOT_IN:
 818                         gen_relation_in(dfw, DFVM_SET_ANY_NOT_IN, st_how, st_arg1, st_arg2);
 819                         break;
 820
 821                 case STNODE_OP_UNINITIALIZED:
 822                 case STNODE_OP_BITWISE_AND:
 823                 case STNODE_OP_UNARY_MINUS:
 824                 case STNODE_OP_ADD:
 825                 case STNODE_OP_SUBTRACT:
 826                 case STNODE_OP_MULTIPLY:
 827                 case STNODE_OP_DIVIDE:
 828                 case STNODE_OP_MODULO:
 829                         ASSERT_STNODE_OP_NOT_REACHED(st_op);
 830         }
 831 }
 832
 833 static dfvm_value_t*
 834 gencode(dfwork_t *dfw, stnode_t *st_node)
 835 {
 836         dfvm_value_t* val = NULL;
 837         /* If the root of the tree is a field, load and return the
 838          * values if we were asked to do so. If not, or anywhere
 839          * other than the root, just test for existence.
 840          */
 841         bool return_val = dfw->flags & DF_RETURN_VALUES;
 842         dfw->flags &= ~DF_RETURN_VALUES;
 843         switch (stnode_type_id(st_node)) {
 844                 case STTYPE_TEST:
 845                         gen_test(dfw, st_node);
 846                         break;
 847                 case STTYPE_FIELD:
 848                         if (return_val) {
 849                                 val = gen_field(dfw, st_node);
 850                         } else {
 851                                 gen_exists(dfw, st_node);
 852                         }
 853                         break;
 854                 case STTYPE_ARITHMETIC:
 855                 case STTYPE_FUNCTION:
 856                         val = gen_notzero(dfw, st_node);
 857                         break;
 858                 case STTYPE_SLICE:
 859                         val = gen_notzero_slice(dfw, st_node);
 860                         break;
 861                 default:
 862                         ASSERT_STTYPE_NOT_REACHED(stnode_type_id(st_node));
 863         }
 864         return val;
 865 }
 866
 867
 868 static void
 869 optimize(dfwork_t *dfw)
 870 {
 871         int             id, id1, length;
 872         dfvm_insn_t     *insn, *insn1, *prev;
 873         dfvm_value_t    *arg1;
 874
 875         length = dfw->insns->len;
 876
 877         for (id = 0, prev = NULL; id < length; prev = insn, id++) {
 878                 insn = (dfvm_insn_t     *)g_ptr_array_index(dfw->insns, id);
 879                 arg1 = insn->arg1;
 880                 if (insn->op == DFVM_IF_TRUE_GOTO || insn->op == DFVM_IF_FALSE_GOTO) {
 881                         id1 = arg1->value.numeric;
 882
 883                         /* If the branch jumps to the next instruction replace it with a no-op. */
 884                         if (id1 == id + 1) {
 885                                 dfvm_insn_replace_no_op(insn);
 886                                 continue;
 887                         }
 888
 889                         /* Try to optimize branch jumps */
 890                         dfvm_opcode_t revert = (insn->op == DFVM_IF_FALSE_GOTO) ? DFVM_IF_TRUE_GOTO : DFVM_IF_FALSE_GOTO;
 891                         for (;;) {
 892                                 insn1 = (dfvm_insn_t*)g_ptr_array_index(dfw->insns, id1);
 893                                 if (insn1->op == revert) {
 894                                         /* Skip this one; it is always false and the branch is not taken */
 895                                         id1 = id1 +1;
 896                                         continue;
 897                                 }
 898                                 if (insn1->op == DFVM_READ_TREE && prev && prev->op == DFVM_READ_TREE &&
 899                                                 prev->arg2->value.numeric == insn1->arg2->value.numeric) {
 900                                         /* Skip this one; hack if it's the same register it's the same field
 901                                          * and it returns the same value */
 902                                         id1 = id1 +1;
 903                                         continue;
 904                                 }
 905                                 if (insn1->op == insn->op) {
 906                                         /* The branch jumps to the same branch instruction so
 907                                          * coalesce the jumps */
 908                                         arg1 = insn1->arg1;
 909                                         id1 = arg1->value.numeric;
 910                                         continue;
 911                                 }
 912                                 /* Finished */
 913                                 arg1 = insn->arg1;
 914                                 arg1->value.numeric = id1;
 915                                 break;
 916                         }
 917                 }
 918         }
 919 }
 920
 921 void
 922 dfw_gencode(dfwork_t *dfw)
 923 {
 924         dfw->insns = g_ptr_array_new();
 925         dfw->loaded_fields = g_hash_table_new(g_direct_hash, g_direct_equal);
 926         dfw->loaded_raw_fields = g_hash_table_new(g_direct_hash, g_direct_equal);
 927         dfw->interesting_fields = g_hash_table_new(g_int_hash, g_int_equal);
 928         dfvm_insn_t *insn = dfvm_insn_new(DFVM_RETURN);
 929         insn->arg1 = dfvm_value_ref(gencode(dfw, dfw->st_root));
 930         dfw_append_insn(dfw, insn);
 931         if (dfw->flags & DF_OPTIMIZE) {
 932                 optimize(dfw);
 933         }
 934 }
 935
 936
 937 typedef struct {
 938         int i;
 939         int *fields;
 940 } hash_key_iterator;
 941
 942 static void
 943 get_hash_key(void *key, void *value _U_, void *user_data)
 944 {
 945         int field_id = *(int *)key;
 946         hash_key_iterator *hki = (hash_key_iterator *)user_data;
 947
 948         hki->fields[hki->i] = field_id;
 949         hki->i++;
 950 }
 951
 952 int*
 953 dfw_interesting_fields(dfwork_t *dfw, int *caller_num_fields)
 954 {
 955         int num_fields = g_hash_table_size(dfw->interesting_fields);
 956
 957         hash_key_iterator hki;
 958
 959         if (num_fields == 0) {
 960                 *caller_num_fields = 0;
 961                 return NULL;
 962         }
 963
 964         hki.fields = g_new(int, num_fields);
 965         hki.i = 0;
 966
 967         g_hash_table_foreach(dfw->interesting_fields, get_hash_key, &hki);
 968         *caller_num_fields = num_fields;
 969         return hki.fields;
 970 }
 971
 972 /*
 973  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 974  *
 975  * Local variables:
 976  * c-basic-offset: 8
 977  * tab-width: 8
 978  * indent-tabs-mode: t
 979  * End:
 980  *
 981  * vi: set shiftwidth=8 tabstop=8 noexpandtab:
 982  * :indentSize=8:tabSize=8:noTabs=false:
 983  */