smatch_kernel_host_data.c

   1 /*
   2  * Copyright (C) 2011 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /* The below code is an adjustment of the smatch_kernel_user_data.c to
  19  * track (untrusted and potentially malicious) data received by a guest
  20  * kernel via various low-level port IO, MMIO, MSR, CPUID and PCI config
  21  * space access functions (see func_table for a full list) from an
  22  * untrusted host/VMM under confidential computing threat model
  23  * (where a guest VM does not trust the host/VMM).
  24  * We call this data as 'host' data here. Being able to track host data
  25  * allows creating new smatch patterns that can perform various checks
  26  * on such data, i.e. verify that that there are no spectre v1 gadgets
  27  * on this attack surface or even simply report locations where host data
  28  * is being processed in the kernel source code (useful for a targeted code
  29  * audit).
  30  * Similar as smatch_kernel_user_data.c it works with
  31  * smatch_points_to_host_input.c code.
  32  *
  33  * Copyright (C) 2022 Elena Reshetova Intel Corporation.
  34  */
  35
  36 #include "smatch.h"
  37 #include "smatch_slist.h"
  38 #include "smatch_extra.h"
  39
  40 struct host_fn_info {
  41         const char *name;
  42         int type;
  43         int param;
  44         const char *key;
  45         const sval_t *implies_start, *implies_end;
  46         func_hook *call_back;
  47 };
  48
  49 static struct host_fn_info func_table[] = {
  50           /* Functions that return host data as return value */
  51         { "inb", HOST_DATA, -1, "$" },
  52         { "inw", HOST_DATA, -1, "$" },
  53         { "inl", HOST_DATA, -1, "$" },
  54         { "__inb", HOST_DATA, -1, "$" },
  55         { "__inw", HOST_DATA, -1, "$" },
  56         { "__inl", HOST_DATA, -1, "$" },
  57         { "ioread8", HOST_DATA, -1, "$" },
  58         { "ioread16", HOST_DATA, -1, "$" },
  59         { "ioread32", HOST_DATA, -1, "$" },
  60         { "ioread16be", HOST_DATA, -1, "$" },
  61         { "ioread32be", HOST_DATA, -1, "$" },
  62         { "ioread64_lo_hi", HOST_DATA, -1, "$" },
  63         { "ioread64_hi_lo", HOST_DATA, -1, "$" },
  64         { "ioread64be_lo_hi", HOST_DATA, -1, "$" },
  65         { "ioread64be_hi_lo", HOST_DATA, -1, "$" },
  66         { "iomap_readq", HOST_DATA, -1, "$" },
  67         { "iomap_readb", HOST_DATA, -1, "$" },
  68         { "iomap_readw", HOST_DATA, -1, "$" },
  69         { "iomap_readl", HOST_DATA, -1, "$" },
  70         { "readb", HOST_DATA, -1, "$" },
  71         { "readw", HOST_DATA, -1, "$" },
  72         { "readl", HOST_DATA, -1, "$" },
  73         { "readq", HOST_DATA, -1, "$" },
  74         { "__raw_readb", HOST_DATA, -1, "$" },
  75         { "__raw_readw", HOST_DATA, -1, "$" },
  76         { "__raw_readl", HOST_DATA, -1, "$" },
  77         { "__raw_readq", HOST_DATA, -1, "$" },
  78         { "__readq", HOST_DATA, -1, "$" },
  79         { "__readl", HOST_DATA, -1, "$" },
  80         { "__readb", HOST_DATA, -1, "$" },
  81         { "__readw", HOST_DATA, -1, "$" },
  82         { "native_read_msr", HOST_DATA, -1, "$" },
  83         { "native_read_msr_safe", HOST_DATA, -1, "$" },
  84         { "__rdmsr", HOST_DATA, -1, "$" },
  85         { "paravirt_read_msr", HOST_DATA, -1, "$" },
  86         { "paravirt_read_msr_safe", HOST_DATA, -1, "$" },
  87           /* the below 3 apic funcs are needed
  88            * since they unwrap to apic->read(reg),
  89            * apic->icr_read() and *(APIC_BASE + reg) */
  90         { "apic_read", HOST_DATA, -1, "$" },
  91         { "apic_icr_read", HOST_DATA, -1, "$" },
  92         { "native_apic_mem_read", HOST_DATA, -1, "$" },
  93           /* the below one is x86_apic_ops.io_apic_read */
  94         { "io_apic_read", HOST_DATA, -1, "$" },
  95           /* virtio_cread8/16/32/64 funcs are needed
  96            * since they call vdev->config->get */
  97         { "virtio_cread8", HOST_DATA, -1, "$" },
  98         { "virtio_cread16", HOST_DATA, -1, "$" },
  99         { "virtio_cread32", HOST_DATA, -1, "$" },
 100         { "virtio_cread64", HOST_DATA, -1, "$" },
 101         { "__virtio16_to_cpu", HOST_DATA, -1, "$" },
 102         { "__virtio32_to_cpu", HOST_DATA, -1, "$" },
 103         { "__virtio64_to_cpu", HOST_DATA, -1, "$" },
 104         { "serial_dl_read", HOST_DATA, -1, "$" },
 105         { "serial_in", HOST_DATA, -1, "$" },
 106         { "serial_port_in", HOST_DATA, -1, "$" },
 107         { "cpuid_eax", HOST_DATA, -1, "$" },
 108         { "cpuid_ebx", HOST_DATA, -1, "$" },
 109         { "cpuid_ecx", HOST_DATA, -1, "$" },
 110         { "cpuid_edx", HOST_DATA, -1, "$" },
 111           /* Functions that return host data as argument 1 */
 112         { "memcpy_fromio", HOST_DATA, 0, "*$" },
 113           /* Functions that return host data as argument 2 */
 114         { "acpi_os_read_iomem", HOST_DATA, 1, "*$" },
 115         { "mmio_insb", HOST_DATA, 1, "*$" },
 116         { "mmio_insw", HOST_DATA, 1, "*$" },
 117         { "mmio_insl", HOST_DATA, 1, "*$" },
 118         { "acpi_read_bit_register", HOST_DATA, 1, "*$" },
 119           /* Functions that return host data as argument 3 */
 120         { "rdmsrl_on_cpu", HOST_DATA, 2, "*$" },
 121         { "rdmsrl_safe_on_cpu", HOST_DATA, 2, "*$" },
 122         { "(struct virtio_config_ops)->get", HOST_DATA, 2, "*$" },
 123         { "__virtio_cread_many", HOST_DATA, 2, "*$" },
 124         { "pci_user_read_config_word", HOST_DATA, 2, "*$" },
 125         { "pci_user_read_config_dword", HOST_DATA, 2, "*$" },
 126         { "pci_user_read_config_byte", HOST_DATA, 2, "*$" },
 127           /* Functions that return host data as argument 4 */
 128         { "pci_bus_read_config_byte", HOST_DATA, 3, "*$" },
 129         { "pci_bus_read_config_word", HOST_DATA, 3, "*$" },
 130         { "pci_bus_read_config_dword", HOST_DATA, 3, "*$" },
 131           /* Functions that return host data as arguments 3 and 4 */
 132         { "rdmsr_on_cpu", HOST_DATA, 2, "*$" },
 133         { "rdmsr_on_cpu", HOST_DATA, 3, "*$" },
 134         { "rdmsr_safe_on_cpu", HOST_DATA, 2, "*$" },
 135         { "rdmsr_safe_on_cpu", HOST_DATA, 3, "*$" },
 136           /* Functions that return host data as argument 6 */
 137         { "raw_pci_read", HOST_DATA, 5, "*$" },
 138           /* Functions that return host data as arguments 2-5 */
 139         { "cpuid", HOST_DATA, 1, "*$" },
 140         { "cpuid", HOST_DATA, 2, "*$" },
 141         { "cpuid", HOST_DATA, 3, "*$" },
 142         { "cpuid", HOST_DATA, 4, "*$" },
 143           /* Functions that return host data as arguments 3-6 */
 144         { "cpuid_count", HOST_DATA, 2, "*$" },
 145         { "cpuid_count", HOST_DATA, 3, "*$" },
 146         { "cpuid_count", HOST_DATA, 4, "*$" },
 147         { "cpuid_count", HOST_DATA, 5, "*$" },
 148 };
 149
 150 int get_host_data_fn_param(const char *fn)
 151 {
 152         int ret = 0;
 153
 154         if (!fn)
 155                 return ret;
 156
 157         for (int i = 0; i < ARRAY_SIZE(func_table); i++) {
 158                 if (strcmp(fn, func_table[i].name) == 0) {
 159                         ret = func_table[i].param;
 160                 }
 161         }
 162         if ((!ret) && (is_fn_points_to_host_data(fn))) {
 163                 ret = -1;
 164         }
 165
 166         return ret;
 167 }
 168
 169 static int my_id;
 170 static unsigned long func_gets_host_data;
 171 static struct stree *start_states;
 172
 173 static struct smatch_state *empty_state(struct sm_state *sm)
 174 {
 175         return alloc_estate_empty();
 176 }
 177
 178 static struct smatch_state *new_state(struct symbol *type)
 179 {
 180         struct smatch_state *state;
 181
 182         if (!type || type_is_ptr(type))
 183                 return NULL;
 184
 185         state = alloc_estate_whole(type);
 186         estate_set_new(state);
 187         return state;
 188 }
 189
 190 static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
 191 {
 192         struct smatch_state *kernel = cur->state;
 193         struct smatch_state *extra;
 194         struct smatch_state *state;
 195         struct range_list *rl;
 196
 197         extra = __get_state(SMATCH_EXTRA, cur->name, cur->sym);
 198         if (!extra)
 199                 return;
 200         rl = rl_intersection(estate_rl(kernel), estate_rl(extra));
 201         state = alloc_estate_rl(clone_rl(rl));
 202         if (estate_capped(kernel) || is_capped_var_sym(cur->name, cur->sym))
 203                 estate_set_capped(state);
 204         if (estates_equiv(state, cur->state))
 205                 return;
 206         if (estate_new(cur->state))
 207                 estate_set_new(state);
 208         set_state(my_id, cur->name, cur->sym, state);
 209 }
 210
 211 static void extra_nomod_hook(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 212 {
 213         struct smatch_state *host, *new;
 214         struct range_list *rl;
 215
 216         host = __get_state(my_id, name, sym);
 217         if (!host)
 218                 return;
 219
 220         rl = rl_intersection(estate_rl(host), estate_rl(state));
 221         if (rl_equiv(rl, estate_rl(host)))
 222                 return;
 223         new = alloc_estate_rl(rl);
 224         if (estate_capped(host))
 225                 estate_set_capped(new);
 226         set_state(my_id, name, sym, new);
 227 }
 228
 229 static void store_type_info(struct expression *expr, struct smatch_state *state)
 230 {
 231         struct symbol *type;
 232         char *type_str, *member;
 233
 234         if (__in_fake_assign)
 235                 return;
 236
 237         if (!estate_rl(state))
 238                 return;
 239
 240         expr = strip_expr(expr);
 241         if (!expr || expr->type != EXPR_DEREF || !expr->member)
 242                 return;
 243
 244         type = get_type(expr->deref);
 245         if (!type || !type->ident)
 246                 return;
 247
 248         type_str = type_to_str(type);
 249         if (!type_str)
 250                 return;
 251         member = get_member_name(expr);
 252         if (!member)
 253                 return;
 254
 255         sql_insert_function_type_info(HOST_DATA, type_str, member, state->name);
 256 }
 257
 258 static void set_host_data(struct expression *expr, struct smatch_state *state)
 259 {
 260         store_type_info(expr, state);
 261         set_state_expr(my_id, expr, state);
 262 }
 263
 264 static bool host_rl_known(struct expression *expr)
 265 {
 266         struct range_list *rl;
 267         sval_t close_to_max;
 268
 269         if (!get_host_rl(expr, &rl))
 270                 return true;
 271
 272         close_to_max = sval_type_max(rl_type(rl));
 273         close_to_max.value -= 100;
 274
 275         if (sval_cmp(rl_max(rl), close_to_max) >= 0)
 276                 return false;
 277         return true;
 278 }
 279
 280 static bool is_array_index_mask_nospec(struct expression *expr)
 281 {
 282         struct expression *orig;
 283
 284         orig = get_assigned_expr(expr);
 285         if (!orig || orig->type != EXPR_CALL)
 286                 return false;
 287         return sym_name_is("array_index_mask_nospec", orig->fn);
 288 }
 289
 290 static bool binop_capped(struct expression *expr)
 291 {
 292         struct range_list *left_rl;
 293         int comparison;
 294         sval_t sval;
 295
 296         if (expr->op == '-' && get_host_rl(expr->left, &left_rl)) {
 297                 if (host_rl_capped(expr->left))
 298                         return true;
 299                 comparison = get_comparison(expr->left, expr->right);
 300                 if (comparison && show_special(comparison)[0] == '>')
 301                         return true;
 302                 return false;
 303         }
 304
 305         if (expr->op == '&' || expr->op == '%') {
 306                 bool left_host, left_capped, right_host, right_capped;
 307
 308                 if (!get_value(expr->right, &sval) && is_capped(expr->right))
 309                         return true;
 310                 if (is_array_index_mask_nospec(expr->right))
 311                         return true;
 312                 if (is_capped(expr->left))
 313                         return true;
 314                 left_host = is_host_rl(expr->left);
 315                 right_host = is_host_rl(expr->right);
 316                 if (!left_host && !right_host)
 317                         return true;
 318
 319                 left_capped = host_rl_capped(expr->left);
 320                 right_capped = host_rl_capped(expr->right);
 321
 322                 if (left_host && left_capped) {
 323                         if (!right_host)
 324                                 return true;
 325                         if (right_host && right_capped)
 326                                 return true;
 327                         return false;
 328                 }
 329                 if (right_host && right_capped) {
 330                         if (!left_host)
 331                                 return true;
 332                         return false;
 333                 }
 334                 return false;
 335         }
 336
 337         /*
 338          * Generally "capped" means that we capped it to an unknown value.
 339          * This is useful because if Smatch doesn't know what the value is then
 340          * we have to trust that it is correct.  But if we known cap value is
 341          * 100 then we can check if 100 is correct and complain if it's wrong.
 342          *
 343          * So then the problem is with BINOP when we take a capped variable
 344          * plus a host variable which is clamped to a known range (uncapped)
 345          * the result should be capped.
 346          */
 347         if ((host_rl_capped(expr->left) || host_rl_known(expr->left)) &&
 348             (host_rl_capped(expr->right) || host_rl_known(expr->right)))
 349                 return true;
 350         return false;
 351 }
 352
 353 bool host_rl_capped(struct expression *expr)
 354 {
 355         struct smatch_state *state;
 356         struct range_list *rl;
 357         sval_t sval;
 358
 359         expr = strip_expr(expr);
 360         if (!expr)
 361                 return false;
 362         if (get_value(expr, &sval))
 363                 return true;
 364         if (expr->type == EXPR_BINOP)
 365                 return binop_capped(expr);
 366         if ((expr->type == EXPR_PREOP || expr->type == EXPR_POSTOP) &&
 367             (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT))
 368                 return host_rl_capped(expr->unop);
 369         state = get_state_expr(my_id, expr);
 370         if (state)
 371                 return estate_capped(state);
 372
 373         if (!get_host_rl(expr, &rl)) {
 374                 /*
 375                  * The non host data parts of a binop are capped and
 376                  * also empty host rl states are capped.
 377                  */
 378                 return true;
 379         }
 380
 381         if (rl_to_sval(rl, &sval))
 382                 return true;
 383
 384         return false;  /* uncapped host data */
 385 }
 386
 387 static void tag_inner_struct_members(struct expression *expr, struct symbol *member)
 388 {
 389         struct expression *edge_member;
 390         struct symbol *base = get_real_base_type(member);
 391         struct symbol *tmp;
 392
 393         if (member->ident)
 394                 expr = member_expression(expr, '.', member->ident);
 395
 396         FOR_EACH_PTR(base->symbol_list, tmp) {
 397                 struct symbol *type;
 398
 399                 type = get_real_base_type(tmp);
 400                 if (!type)
 401                         continue;
 402
 403                 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
 404                         tag_inner_struct_members(expr, tmp);
 405                         continue;
 406                 }
 407
 408                 if (!tmp->ident)
 409                         continue;
 410
 411                 edge_member = member_expression(expr, '.', tmp->ident);
 412                 set_host_data(edge_member, new_state(type));
 413         } END_FOR_EACH_PTR(tmp);
 414 }
 415
 416 static void tag_struct_members(struct symbol *type, struct expression *expr)
 417 {
 418         struct symbol *tmp;
 419         struct expression *member;
 420         int op = '*';
 421
 422         if (expr->type == EXPR_PREOP && expr->op == '&') {
 423                 expr = strip_expr(expr->unop);
 424                 op = '.';
 425         }
 426
 427         FOR_EACH_PTR(type->symbol_list, tmp) {
 428                 type = get_real_base_type(tmp);
 429                 if (!type)
 430                         continue;
 431
 432                 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
 433                         tag_inner_struct_members(expr, tmp);
 434                         continue;
 435                 }
 436
 437                 if (!tmp->ident)
 438                         continue;
 439
 440                 member = member_expression(expr, op, tmp->ident);
 441                 if (type->type == SYM_ARRAY) {
 442                         set_points_to_host_data(member, true);
 443                 } else {
 444                         set_host_data(member, new_state(get_type(member)));
 445                 }
 446         } END_FOR_EACH_PTR(tmp);
 447 }
 448
 449 static void tag_base_type(struct expression *expr)
 450 {
 451         if (expr->type == EXPR_PREOP && expr->op == '&')
 452                 expr = strip_expr(expr->unop);
 453         else
 454                 expr = deref_expression(expr);
 455         set_host_data(expr, new_state(get_type(expr)));
 456 }
 457
 458 static void tag_as_host_data(struct expression *expr)
 459 {
 460         struct symbol *type;
 461
 462         expr = strip_expr(expr);
 463         type = get_type(expr);
 464
 465         if (!type)
 466                 return;
 467
 468         if (type->type == SYM_PTR){
 469                 type = get_real_base_type(type);
 470                 if (!type)
 471                         return;
 472                 if (type == &void_ctype) {
 473                         set_host_data(deref_expression(expr), new_state(&ulong_ctype));
 474                         return;
 475                 }
 476                 if (type->type == SYM_BASETYPE) {
 477                         if (expr->type != EXPR_PREOP && expr->op != '&')
 478                                 set_points_to_host_data(expr, true);
 479                         tag_base_type(expr);
 480                         return;
 481                 }
 482                 if (type->type == SYM_STRUCT || type->type == SYM_UNION) {
 483                         if (expr->type != EXPR_PREOP || expr->op != '&')
 484                                 expr = deref_expression(expr);
 485                         else
 486                                 set_host_data(deref_expression(expr), new_state(&ulong_ctype));
 487                         tag_struct_members(type, expr);
 488                 }
 489                 return;
 490         }
 491
 492         if (expr->type == EXPR_DEREF) {
 493                 type = get_type(expr->deref);
 494                 expr = strip_expr(expr->deref);
 495
 496                 if (!type){
 497                         sm_msg("%s: no type\n", __func__);
 498                         return;
 499                 }
 500         }
 501
 502         if (type->type == SYM_BASETYPE) {
 503                 if (expr->type == EXPR_PREOP && expr->op == '*')
 504                         set_points_to_host_data(expr->unop, true);
 505                 set_host_data(expr, new_state(get_type(expr)));
 506                 return;
 507         }
 508         if (type->type == SYM_STRUCT || type->type == SYM_UNION) {
 509                 set_host_data(expr, new_state(&ulong_ctype));
 510                 tag_struct_members(type, expr);
 511         }
 512 }
 513
 514 static int get_rl_from_function(struct expression *expr, struct range_list **rl)
 515 {
 516         if (!expr)
 517                 return 0;
 518
 519         if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL ||
 520             !expr->fn->symbol_name)
 521                 return 0;
 522
 523         for (int i = 0; i < ARRAY_SIZE(func_table); i++) {
 524                 if ((strcmp(expr->fn->symbol_name->name, func_table[i].name) == 0) &&
 525                    (func_table[i].param == -1)) {
 526                         *rl = alloc_whole_rl(get_type(expr));
 527                         return 1;
 528                 }
 529         }
 530         return 0;
 531 }
 532
 533 static bool state_is_new(struct expression *expr)
 534 {
 535         struct smatch_state *state;
 536
 537         state = get_state_expr(my_id, expr);
 538         if (estate_new(state))
 539                 return true;
 540
 541         if (expr->type == EXPR_BINOP) {
 542                 if (state_is_new(expr->left))
 543                         return true;
 544                 if (state_is_new(expr->right))
 545                         return true;
 546         }
 547         return false;
 548 }
 549
 550 static void handle_derefed_pointers(struct expression *expr, bool is_new)
 551 {
 552         expr = strip_expr(expr);
 553         if (expr->type != EXPR_PREOP ||
 554             expr->op != '*')
 555                 return;
 556         expr = strip_expr(expr->unop);
 557         set_points_to_host_data(expr, is_new);
 558 }
 559
 560 static bool handle_op_assign(struct expression *expr)
 561 {
 562         struct expression *binop_expr;
 563         struct smatch_state *state;
 564         struct range_list *rl;
 565         bool is_new;
 566
 567         switch (expr->op) {
 568         case SPECIAL_ADD_ASSIGN:
 569         case SPECIAL_SUB_ASSIGN:
 570         case SPECIAL_AND_ASSIGN:
 571         case SPECIAL_MOD_ASSIGN:
 572         case SPECIAL_SHL_ASSIGN:
 573         case SPECIAL_SHR_ASSIGN:
 574         case SPECIAL_OR_ASSIGN:
 575         case SPECIAL_XOR_ASSIGN:
 576         case SPECIAL_MUL_ASSIGN:
 577         case SPECIAL_DIV_ASSIGN:
 578                 binop_expr = binop_expression(expr->left,
 579                                               op_remove_assign(expr->op),
 580                                               expr->right);
 581                 if (!get_host_rl(binop_expr, &rl))
 582                         return true;
 583                 rl = cast_rl(get_type(expr->left), rl);
 584                 state = alloc_estate_rl(rl);
 585                 if (expr->op == SPECIAL_AND_ASSIGN ||
 586                     expr->op == SPECIAL_MOD_ASSIGN ||
 587                     host_rl_capped(binop_expr))
 588                         estate_set_capped(state);
 589                 is_new = state_is_new(binop_expr);
 590                 if (is_new)
 591                         estate_set_new(state);
 592                 estate_set_assigned(state);
 593                 set_host_data(expr->left, state);
 594                 handle_derefed_pointers(expr->left, is_new);
 595                 return true;
 596         }
 597         return false;
 598 }
 599
 600 static struct range_list *strip_negatives(struct range_list *rl)
 601 {
 602         sval_t min = rl_min(rl);
 603         sval_t minus_one = { .type = rl_type(rl), .value = -1 };
 604         sval_t over = { .type = rl_type(rl), .value = INT_MAX + 1ULL };
 605         sval_t max = sval_type_max(rl_type(rl));
 606
 607         if (!rl)
 608                 return NULL;
 609
 610         if (type_unsigned(rl_type(rl)) && type_bits(rl_type(rl)) > 31)
 611                 return remove_range(rl, over, max);
 612
 613         return remove_range(rl, min, minus_one);
 614 }
 615
 616 static void match_assign_host(struct expression *expr)
 617 {
 618         struct symbol *left_type, *right_type;
 619         struct range_list *rl = NULL;
 620         static struct expression *handled;
 621         struct smatch_state *state;
 622         struct expression *faked;
 623         bool is_capped = false;
 624         bool is_new = false;
 625
 626         if (!expr)
 627                 return;
 628
 629         left_type = get_type(expr->left);
 630         if (left_type == &void_ctype)
 631                 return;
 632
 633         faked = get_faked_expression();
 634
 635         /* FIXME: handle fake array assignments frob(&host_array[x]); */
 636
 637         if (faked &&
 638             faked->type == EXPR_ASSIGNMENT &&
 639             points_to_host_data(faked->right)) {
 640                 rl = alloc_whole_rl(get_type(expr->left));
 641                 is_new = true;
 642                 goto set;
 643         }
 644
 645         if (faked && faked == handled)
 646                 return;
 647         if (is_fake_call(expr->right))
 648                 goto clear_old_state;
 649         if (points_to_host_data(expr->right) &&
 650             is_struct_ptr(get_type(expr->left))) {
 651                 handled = expr;
 652                 // This should be handled by smatch_points_to_host_data.c
 653                 //set_points_to_host_data(expr->left);
 654         }
 655
 656         if (handle_op_assign(expr))
 657                 return;
 658         if (expr->op != '=')
 659                 goto clear_old_state;
 660
 661         /* Handled by DB code */
 662         if (expr->right->type == EXPR_CALL)
 663                 return;
 664
 665         if (faked)
 666                 disable_type_val_lookups();
 667         get_host_rl(expr->right, &rl);
 668         if (faked)
 669                 enable_type_val_lookups();
 670         if (!rl)
 671                 goto clear_old_state;
 672
 673         is_capped = host_rl_capped(expr->right);
 674         is_new = state_is_new(expr->right);
 675
 676 set:
 677         right_type = get_type(expr->right);
 678         if (type_is_ptr(left_type)) {
 679                 if (right_type && right_type->type == SYM_ARRAY)
 680                         set_points_to_host_data(expr->left, is_new);
 681                 return;
 682         }
 683
 684         rl = cast_rl(left_type, rl);
 685         if (is_capped && type_unsigned(right_type) && type_signed(left_type))
 686                 rl = strip_negatives(rl);
 687         state = alloc_estate_rl(rl);
 688         if (is_new)
 689                 estate_set_new(state);
 690         if (is_capped)
 691                 estate_set_capped(state);
 692         estate_set_assigned(state);
 693         set_host_data(expr->left, state);
 694         handle_derefed_pointers(expr->left, is_new);
 695         return;
 696
 697 clear_old_state:
 698
 699         /*
 700          * HACK ALERT!!!  This should be at the start of the function.  The
 701          * the problem is that handling "pointer = array;" assignments is
 702          * handled in this function instead of in kernel_points_to_host_data.c.
 703          */
 704         if (type_is_ptr(left_type))
 705                 return;
 706
 707         if (get_state_expr(my_id, expr->left))
 708                 set_host_data(expr->left, alloc_estate_empty());
 709 }
 710
 711 static void handle_eq_noteq(struct expression *expr)
 712 {
 713         struct smatch_state *left_orig, *right_orig;
 714
 715         left_orig = get_state_expr(my_id, expr->left);
 716         right_orig = get_state_expr(my_id, expr->right);
 717
 718         if (!left_orig && !right_orig)
 719                 return;
 720         if (left_orig && right_orig)
 721                 return;
 722
 723         if (left_orig) {
 724                 set_true_false_states_expr(my_id, expr->left,
 725                                 expr->op == SPECIAL_EQUAL ? alloc_estate_empty() : NULL,
 726                                 expr->op == SPECIAL_EQUAL ? NULL : alloc_estate_empty());
 727         } else {
 728                 set_true_false_states_expr(my_id, expr->right,
 729                                 expr->op == SPECIAL_EQUAL ? alloc_estate_empty() : NULL,
 730                                 expr->op == SPECIAL_EQUAL ? NULL : alloc_estate_empty());
 731         }
 732 }
 733
 734 static void handle_compare(struct expression *expr)
 735 {
 736         struct expression  *left, *right;
 737         struct range_list *left_rl = NULL;
 738         struct range_list *right_rl = NULL;
 739         struct range_list *host_rl;
 740         struct smatch_state *capped_state;
 741         struct smatch_state *left_true = NULL;
 742         struct smatch_state *left_false = NULL;
 743         struct smatch_state *right_true = NULL;
 744         struct smatch_state *right_false = NULL;
 745         struct symbol *type;
 746         sval_t sval;
 747
 748         left = strip_expr(expr->left);
 749         right = strip_expr(expr->right);
 750
 751         while (left->type == EXPR_ASSIGNMENT)
 752                 left = strip_expr(left->left);
 753
 754         /*
 755          * Conditions are mostly handled by smatch_extra.c, but there are some
 756          * times where the exact values are not known so we can't do that.
 757          *
 758          * Normally, we might consider using smatch_capped.c to supliment smatch
 759          * extra but that doesn't work when we merge unknown uncapped kernel
 760          * data with unknown capped host data.  The result is uncapped host
 761          * data.  We need to keep it separate and say that the host data is
 762          * capped.  In the past, I would have marked this as just regular
 763          * kernel data (not host data) but we can't do that these days because
 764          * we need to track host data for Spectre.
 765          *
 766          * The other situation which we have to handle is when we do have an
 767          * int and we compare against an unknown unsigned kernel variable.  In
 768          * that situation we assume that the kernel data is less than INT_MAX.
 769          * Otherwise then we get all sorts of array underflow false positives.
 770          *
 771          */
 772
 773         /* Handled in smatch_extra.c */
 774         if (get_implied_value(left, &sval) ||
 775             get_implied_value(right, &sval))
 776                 return;
 777
 778         get_host_rl(left, &left_rl);
 779         get_host_rl(right, &right_rl);
 780
 781         /* nothing to do */
 782         if (!left_rl && !right_rl)
 783                 return;
 784         /* if both sides are host data that's not a good limit */
 785         if (left_rl && right_rl)
 786                 return;
 787
 788         if (left_rl)
 789                 host_rl = left_rl;
 790         else
 791                 host_rl = right_rl;
 792
 793         type = get_type(expr);
 794         if (type_unsigned(type))
 795                 host_rl = strip_negatives(host_rl);
 796         capped_state = alloc_estate_rl(host_rl);
 797         estate_set_capped(capped_state);
 798
 799         switch (expr->op) {
 800         case '<':
 801         case SPECIAL_UNSIGNED_LT:
 802         case SPECIAL_LTE:
 803         case SPECIAL_UNSIGNED_LTE:
 804                 if (left_rl)
 805                         left_true = capped_state;
 806                 else
 807                         right_false = capped_state;
 808                 break;
 809         case '>':
 810         case SPECIAL_UNSIGNED_GT:
 811         case SPECIAL_GTE:
 812         case SPECIAL_UNSIGNED_GTE:
 813                 if (left_rl)
 814                         left_false = capped_state;
 815                 else
 816                         right_true = capped_state;
 817                 break;
 818         }
 819         set_true_false_states_expr(my_id, left, left_true, left_false);
 820         set_true_false_states_expr(my_id, right, right_true, right_false);
 821 }
 822
 823 static void match_condition_host(struct expression *expr)
 824 {
 825         if (!expr)
 826                 return;
 827
 828         if (expr->type != EXPR_COMPARE)
 829                 return;
 830
 831         if (expr->op == SPECIAL_EQUAL ||
 832             expr->op == SPECIAL_NOTEQUAL) {
 833                 handle_eq_noteq(expr);
 834                 return;
 835         }
 836         handle_compare(expr);
 837 }
 838
 839 static void match_returns_host_rl(const char *fn, struct expression *expr, void *unused)
 840 {
 841         func_gets_host_data = true;
 842 }
 843
 844 static int has_host_data(struct symbol *sym)
 845 {
 846         struct sm_state *tmp;
 847
 848         FOR_EACH_MY_SM(my_id, __get_cur_stree(), tmp) {
 849                 if (tmp->sym == sym)
 850                         return 1;
 851         } END_FOR_EACH_SM(tmp);
 852         return 0;
 853 }
 854
 855 bool we_pass_host_data(struct expression *call)
 856 {
 857         struct expression *arg;
 858         struct symbol *sym;
 859
 860         FOR_EACH_PTR(call->args, arg) {
 861                 if (points_to_host_data(arg))
 862                         return true;
 863                 sym = expr_to_sym(arg);
 864                 if (!sym)
 865                         continue;
 866                 if (has_host_data(sym))
 867                         return true;
 868         } END_FOR_EACH_PTR(arg);
 869
 870         return false;
 871 }
 872
 873 static int db_returned_host_rl(struct expression *call, struct range_list **rl)
 874 {
 875         struct smatch_state *state;
 876         char buf[48];
 877
 878         if (is_fake_call(call))
 879                 return 0;
 880         snprintf(buf, sizeof(buf), "return %p", call);
 881         state = get_state(my_id, buf, NULL);
 882         if (!state || !estate_rl(state))
 883                 return 0;
 884         *rl = estate_rl(state);
 885         return 1;
 886 }
 887
 888 struct stree *get_host_stree(void)
 889 {
 890         return get_all_states_stree(my_id);
 891 }
 892
 893 static int host_data_flag;
 894 static int no_host_data_flag;
 895
 896 struct range_list *var_host_rl(struct expression *expr)
 897 {
 898         struct smatch_state *state;
 899         struct range_list *rl;
 900         struct range_list *absolute_rl;
 901
 902         if (expr->type == EXPR_PREOP && expr->op == '&') {
 903                 no_host_data_flag = 1;
 904                 return NULL;
 905         }
 906
 907         if (expr->type == EXPR_BINOP && expr->op == '%') {
 908                 struct range_list *left, *right;
 909
 910                 if (!get_host_rl(expr->right, &right))
 911                         return NULL;
 912                 get_absolute_rl(expr->left, &left);
 913                 rl = rl_binop(left, '%', right);
 914                 goto found;
 915         }
 916
 917         if (expr->type == EXPR_BINOP && expr->op == '/') {
 918                 struct range_list *left = NULL;
 919                 struct range_list *right = NULL;
 920                 struct range_list *abs_right;
 921
 922                 get_host_rl(expr->left, &left);
 923                 get_host_rl(expr->right, &right);
 924                 get_absolute_rl(expr->right, &abs_right);
 925
 926                 if (left && !right) {
 927                         rl = rl_binop(left, '/', abs_right);
 928                         if (sval_cmp(rl_max(left), rl_max(rl)) < 0)
 929                                 no_host_data_flag = 1;
 930                 }
 931
 932                 return NULL;
 933         }
 934
 935         if (get_rl_from_function(expr, &rl))
 936                 goto found;
 937
 938         state = get_state_expr(my_id, expr);
 939         if (state && estate_rl(state)) {
 940                 rl = estate_rl(state);
 941                 goto found;
 942         }
 943
 944         if (expr->type == EXPR_CALL && db_returned_host_rl(expr, &rl))
 945                 goto found;
 946
 947         if (expr->type == EXPR_PREOP && expr->op == '*' &&
 948             points_to_host_data(expr->unop)) {
 949                 rl = var_to_absolute_rl(expr);
 950                 goto found;
 951         }
 952
 953         if (is_array(expr)) {
 954                 struct expression *array = get_array_base(expr);
 955
 956                 if (!get_state_expr(my_id, array)) {
 957                         no_host_data_flag = 1;
 958                         return NULL;
 959                 }
 960         }
 961
 962         return NULL;
 963 found:
 964         host_data_flag = 1;
 965         absolute_rl = var_to_absolute_rl(expr);
 966         return clone_rl(rl_intersection(rl, absolute_rl));
 967 }
 968
 969 static bool is_ptr_subtract(struct expression *expr)
 970 {
 971         expr = strip_expr(expr);
 972         if (!expr)
 973                 return false;
 974         if (expr->type == EXPR_BINOP && expr->op == '-' &&
 975             type_is_ptr(get_type(expr->left))) {
 976                 return true;
 977         }
 978         return false;
 979 }
 980
 981 int get_host_rl(struct expression *expr, struct range_list **rl)
 982 {
 983         if (is_ptr_subtract(expr))
 984                 return 0;
 985
 986         host_data_flag = 0;
 987         no_host_data_flag = 0;
 988         custom_get_absolute_rl(expr, &var_host_rl, rl);
 989         if (!host_data_flag || no_host_data_flag)
 990                 *rl = NULL;
 991         return !!*rl;
 992 }
 993
 994 int is_host_rl(struct expression *expr)
 995 {
 996         struct range_list *tmp;
 997
 998         return get_host_rl(expr, &tmp) && tmp;
 999 }
1000
1001 int get_host_rl_var_sym(const char *name, struct symbol *sym, struct range_list **rl)
1002 {
1003         struct smatch_state *state;
1004
1005         state = get_state(my_id, name, sym);
1006         if (state && estate_rl(state)) {
1007                 *rl = estate_rl(state);
1008                 return 1;
1009         }
1010         return 0;
1011 }
1012
1013 static void return_info_callback_host(int return_id, char *return_ranges,
1014                                  struct expression *returned_expr,
1015                                  int param,
1016                                  const char *printed_name,
1017                                  struct sm_state *sm)
1018 {
1019         struct smatch_state *extra;
1020         struct range_list *rl;
1021         char buf[64];
1022
1023         if (is_ignored_kernel_data(printed_name))
1024                 return;
1025
1026         if (param >= 0) {
1027                 if (strcmp(printed_name, "$") == 0)
1028                         return;
1029                 if (!estate_assigned(sm->state) &&
1030                     !estate_new(sm->state))
1031                         return;
1032         }
1033         rl = estate_rl(sm->state);
1034         if (!rl)
1035                 return;
1036         extra = get_state(SMATCH_EXTRA, sm->name, sm->sym);
1037         if (estate_rl(extra))
1038                 rl = rl_intersection(estate_rl(sm->state), estate_rl(extra));
1039         if (!rl)
1040                 return;
1041
1042         snprintf(buf, sizeof(buf), "%s%s%s",
1043                  show_rl(rl),
1044                  estate_capped(sm->state) ? "[c]" : "", "");
1045         sql_insert_return_states(return_id, return_ranges,
1046                                  estate_new(sm->state) ? HOST_DATA_SET : HOST_DATA,
1047                                  param, printed_name, buf);
1048
1049 }
1050
1051 static void caller_info_callback_host(struct expression *call, int param, char *printed_name, struct sm_state *sm)
1052 {
1053         struct smatch_state *state;
1054         struct range_list *rl;
1055         struct symbol *type;
1056         char buf[64];
1057
1058         /*
1059          * Smatch uses a hack where if we get an unsigned long we say it's
1060          * both host data and it points to host data.  But if we pass it to a
1061          * function which takes an int, then it's just host data.  There's not
1062          * enough bytes for it to be a pointer.
1063          *
1064          */
1065         type = get_arg_type(call->fn, param);
1066         if (strcmp(printed_name, "$") != 0 && type && type_bits(type) < type_bits(&ptr_ctype))
1067                 return;
1068
1069         if (is_ignored_kernel_data(printed_name))
1070                 return;
1071
1072         if (strcmp(sm->state->name, "") == 0)
1073                 return;
1074
1075         state = __get_state(SMATCH_EXTRA, sm->name, sm->sym);
1076         if (!state || !estate_rl(state))
1077                 rl = estate_rl(sm->state);
1078         else
1079                 rl = rl_intersection(estate_rl(sm->state), estate_rl(state));
1080
1081         if (!rl)
1082                 return;
1083
1084         snprintf(buf, sizeof(buf), "%s%s%s", show_rl(rl),
1085                  estate_capped(sm->state) ? "[c]" : "", "");
1086         sql_insert_caller_info(call, HOST_DATA, param, printed_name, buf);
1087 }
1088
1089 static void db_param_set(struct expression *expr, int param, char *key, char *value)
1090 {
1091         struct expression *arg;
1092         char *name;
1093         struct symbol *sym;
1094         struct smatch_state *state;
1095
1096         while (expr->type == EXPR_ASSIGNMENT)
1097                 expr = strip_expr(expr->right);
1098         if (expr->type != EXPR_CALL)
1099                 return;
1100
1101         arg = get_argument_from_call_expr(expr->args, param);
1102         if (!arg)
1103                 return;
1104
1105         name = get_variable_from_key(arg, key, &sym);
1106         if (!name || !sym)
1107                 goto free;
1108
1109         state = get_state(my_id, name, sym);
1110         if (!state)
1111                 goto free;
1112
1113         set_state(my_id, name, sym, alloc_estate_empty());
1114 free:
1115         free_string(name);
1116 }
1117
1118 static bool param_data_capped(const char *value)
1119 {
1120         if (strstr(value, ",c") || strstr(value, "[c"))
1121                 return true;
1122         return false;
1123 }
1124
1125 static void set_param_host_data(const char *name, struct symbol *sym, char *key, char *value)
1126 {
1127         struct expression *expr;
1128         struct range_list *rl = NULL;
1129         struct smatch_state *state;
1130         struct symbol *type;
1131         char *fullname;
1132
1133         expr = symbol_expression(sym);
1134         fullname = get_variable_from_key(expr, key, NULL);
1135         if (!fullname)
1136                 return;
1137
1138         type = get_member_type_from_key(expr, key);
1139         if (type && type->type == SYM_STRUCT)
1140                 return;
1141
1142         if (!type)
1143                 return;
1144
1145         str_to_rl(type, value, &rl);
1146         rl = swap_mtag_seed(expr, rl);
1147         state = alloc_estate_rl(rl);
1148         if (param_data_capped(value) || is_capped(expr))
1149                 estate_set_capped(state);
1150         set_state(my_id, fullname, sym, state);
1151 }
1152
1153 #define OLD 0
1154 #define NEW 1
1155
1156 static void store_host_data_return(struct expression *expr, char *key, char *value, bool is_new)
1157 {
1158         struct smatch_state *state;
1159         struct range_list *rl;
1160         struct symbol *type;
1161         char buf[48];
1162
1163         if (key[0] != '$')
1164                 return;
1165
1166         type = get_type(expr);
1167         snprintf(buf, sizeof(buf), "return %p%s", expr, key + 1);
1168         call_results_to_rl(expr, type, value, &rl);
1169
1170         state = alloc_estate_rl(rl);
1171         if (is_new)
1172                 estate_set_new(state);
1173         set_state(my_id, buf, NULL, state);
1174 }
1175
1176 static void set_to_host_data(struct expression *expr, char *key, char *value, bool is_new)
1177 {
1178         struct smatch_state *state;
1179         char *name;
1180         struct symbol *sym;
1181         struct symbol *type;
1182         struct range_list *rl = NULL;
1183
1184         type = get_member_type_from_key(expr, key);
1185         name = get_variable_from_key(expr, key, &sym);
1186         if (!name || !sym)
1187                 goto free;
1188
1189         call_results_to_rl(expr, type, value, &rl);
1190
1191         state = alloc_estate_rl(rl);
1192         if (param_data_capped(value))
1193                 estate_set_capped(state);
1194         if (is_new)
1195                 estate_set_new(state);
1196         estate_set_assigned(state);
1197         set_state(my_id, name, sym, state);
1198 free:
1199         free_string(name);
1200 }
1201
1202 static void returns_param_host_data(struct expression *expr, int param, char *key, char *value)
1203 {
1204         struct expression *arg;
1205         struct expression *call;
1206
1207         call = expr;
1208         while (call->type == EXPR_ASSIGNMENT)
1209                 call = strip_expr(call->right);
1210         if (call->type != EXPR_CALL)
1211                 return;
1212
1213         if (!we_pass_host_data(call))
1214                 return;
1215
1216         if (param == -1) {
1217                 if (expr->type != EXPR_ASSIGNMENT) {
1218                         store_host_data_return(expr, key, value, OLD);
1219                         return;
1220                 }
1221                 set_to_host_data(expr->left, key, value, OLD);
1222                 return;
1223         }
1224
1225         arg = get_argument_from_call_expr(call->args, param);
1226         if (!arg)
1227                 return;
1228         set_to_host_data(arg, key, value, OLD);
1229 }
1230
1231 static void returns_param_host_data_set(struct expression *expr, int param, char *key, char *value)
1232 {
1233         struct expression *arg;
1234
1235         func_gets_host_data = true;
1236
1237         if (param == -1) {
1238                 if (expr->type != EXPR_ASSIGNMENT) {
1239                         store_host_data_return(expr, key, value, NEW);
1240                         return;
1241                 }
1242                 set_to_host_data(expr->left, key, value, NEW);
1243                 return;
1244         }
1245
1246         while (expr->type == EXPR_ASSIGNMENT)
1247                 expr = strip_expr(expr->right);
1248         if (expr->type != EXPR_CALL)
1249                 return;
1250
1251         arg = get_argument_from_call_expr(expr->args, param);
1252         if (!arg)
1253                 return;
1254         set_to_host_data(arg, key, value, NEW);
1255 }
1256
1257 static void returns_param_capped_host(struct expression *expr, int param, char *key, char *value)
1258 {
1259         struct smatch_state *state, *new;
1260         struct symbol *sym;
1261         char *name;
1262
1263         name = get_name_sym_from_param_key(expr, param, key, &sym);
1264         if (!name || !sym)
1265                 goto free;
1266
1267         state = get_state(my_id, name, sym);
1268         if (!state || estate_capped(state))
1269                 goto free;
1270
1271         new = clone_estate(state);
1272         estate_set_capped(new);
1273
1274         set_state(my_id, name, sym, new);
1275 free:
1276         free_string(name);
1277 }
1278
1279 struct param_key_data {
1280         param_key_hook *call_back;
1281         int param;
1282         const char *key;
1283         void *info;
1284 };
1285
1286 static void match_function_def(struct symbol *sym)
1287 {
1288         if (is_host_data_fn(sym))
1289                 func_gets_host_data = true;
1290 }
1291
1292 static void set_param_host_input_data(struct expression *expr, const char *name,
1293                                  struct symbol *sym, void *data)
1294 {
1295         struct expression *arg;
1296
1297         func_gets_host_data = true;
1298         arg = gen_expression_from_name_sym(name, sym);
1299         tag_as_host_data(arg);
1300 }
1301
1302 void register_kernel_host_data(int id)
1303 {
1304         int i;
1305         struct host_fn_info *info;
1306
1307         my_id = id;
1308
1309         if (option_project != PROJ_KERNEL)
1310                 return;
1311
1312         set_dynamic_states(my_id);
1313         add_function_data(&func_gets_host_data);
1314         add_hook(&match_function_def, FUNC_DEF_HOOK);
1315
1316         add_function_data((unsigned long *)&start_states);
1317         add_unmatched_state_hook(my_id, &empty_state);
1318         add_extra_nomod_hook(&extra_nomod_hook);
1319         add_pre_merge_hook(my_id, &pre_merge_hook);
1320         add_merge_hook(my_id, &merge_estates);
1321
1322
1323         for (i = 0; i < ARRAY_SIZE(func_table); i++) {
1324                 info = &func_table[i];
1325                 add_function_param_key_hook_late(info->name, &set_param_host_input_data,
1326                                                  info->param, info->key, info);
1327         }
1328
1329         for (i = 0; i < ARRAY_SIZE(func_table); i++) {
1330                 if (func_table[i].param == -1)
1331                         add_function_hook(func_table[i].name, &match_returns_host_rl, NULL);
1332         }
1333
1334         add_hook(&match_assign_host, ASSIGNMENT_HOOK);
1335         select_return_states_hook(PARAM_SET, &db_param_set);
1336         add_hook(&match_condition_host, CONDITION_HOOK);
1337
1338         add_caller_info_callback(my_id, caller_info_callback_host);
1339         add_return_info_callback(my_id, return_info_callback_host);
1340         select_caller_info_hook(set_param_host_data, HOST_DATA);
1341         select_return_states_hook(HOST_DATA, &returns_param_host_data);
1342         select_return_states_hook(HOST_DATA_SET, &returns_param_host_data_set);
1343         select_return_states_hook(CAPPED_DATA, &returns_param_capped_host);
1344 }