Add illumos projects

[smatch.git] / smatch_constraints.c

/*
 * Copyright (C) 2017 Oracle.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
 */

/*
 * Basically I see constraints as a way of saying "x <= some_limit".  The
 * problem is that smatch_capped is not granullar enough.
 *
 * This is mostly for finding out of bounds errors.  So there are different
 * types of constraints.  Quite often we have "foo->xxx[i] = 42;" and we want
 * to verify that "i" is less than foo->size.
 *
 * My idea was that we could automatically figure out these constraints.  And we
 * could load them in the DB so that they are the same every time.  As in a
 * constraint could be "< (struct whatever)->size" and give that in ID that
 * would be constant until you completely wiped the DB.  So when you do a normal
 * DB rebuild then the first thing it will do is preserve all the constraints.
 * I guess the reason to do it this way is to save space...  I sometimes suspect
 * that worrying about saving space is premature optimization.
 *
 * The other thing that I want to do a little bit different here is how I merge
 * constraints.  If a constraint is true on both sides, then that's normal.  If
 * we merge constraint 23 and 67 then we get constraint 23|67.  If we merge 23
 * with &undefined then we get &undefined.  We can also have two constraints
 * that are both true so we could have (45&23)|12 which means either both 45 and
 * 23 are true or 12 is true.
 *
 */


#include "smatch.h"
#include "smatch_extra.h"
#include "smatch_slist.h"

static int my_id;

ALLOCATOR(constraint, "constraints");

static void add_constraint(struct constraint_list **list, int op, int constraint)
{
        struct constraint *tmp, *new;

        FOR_EACH_PTR(*list, tmp) {
                if (tmp->id < constraint)
                        continue;
                if (tmp->id == constraint) {
                        if (tmp->op == '<')
                                return;
                        if (op == SPECIAL_LTE)
                                return;

                        new = __alloc_constraint(0);
                        new->op = op;
                        new->id = constraint;
                        REPLACE_CURRENT_PTR(tmp, new);
                        return;
                }

                new = __alloc_constraint(0);
                new->op = op;
                new->id = constraint;
                INSERT_CURRENT(new, tmp);
                return;
        } END_FOR_EACH_PTR(tmp);

        new = __alloc_constraint(0);
        new->op = op;
        new->id = constraint;
        add_ptr_list(list, new);
}

static struct constraint_list *merge_constraint_lists(struct constraint_list *one, struct constraint_list *two)
{
        struct constraint_list *ret = NULL;
        struct constraint *tmp;

        // FIXME: not || but &&
        FOR_EACH_PTR(one, tmp) {
                add_constraint(&ret, tmp->op, tmp->id);
        } END_FOR_EACH_PTR(tmp);

        FOR_EACH_PTR(two, tmp) {
                add_constraint(&ret, tmp->op, tmp->id);
        } END_FOR_EACH_PTR(tmp);

        return ret;
}

static struct constraint_list *clone_constraint_list(struct constraint_list *list)
{
        struct constraint_list *ret = NULL;
        struct constraint *tmp;

        FOR_EACH_PTR(list, tmp) {
                add_constraint(&ret, tmp->op, tmp->id);
        } END_FOR_EACH_PTR(tmp);

        return ret;
}

static struct smatch_state *alloc_constraint_state(struct constraint_list *list)
{
        struct smatch_state *state;
        struct constraint *con;
        static char buf[256];
        int cnt = 0;

        FOR_EACH_PTR(list, con) {
                if (cnt != 0)
                        cnt += snprintf(buf + cnt, sizeof(buf) - cnt, ", ");
                cnt += snprintf(buf + cnt, sizeof(buf) - cnt, "%s%d",
                                show_special(con->op), con->id);
        } END_FOR_EACH_PTR(con);

        state = __alloc_smatch_state(0);
        state->name = alloc_string(buf);
        state->data = list;
        return state;
}

static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
{
        struct constraint_list *list;

        // FIXME:  use the dead code below instead
        if (strcmp(s1->name, s2->name) == 0)
                return s1;
        return &merged;

        list = merge_constraint_lists(s1->data, s2->data);
        return alloc_constraint_state(list);
}

static int negate_gt(int op)
{
        switch (op) {
        case '>':
        case SPECIAL_UNSIGNED_GT:
        case SPECIAL_GTE:
        case SPECIAL_UNSIGNED_GTE:
                return negate_comparison(op);
        }
        return op;
}

static char *get_func_constraint(struct expression *expr)
{
        char buf[256];
        char *name;

        if (is_fake_call(expr))
                return NULL;
        name = expr_to_str(expr->fn);
        if (!name)
                return NULL;
        snprintf(buf, sizeof(buf), "%s()", name);
        free_string(name);
        return alloc_string(buf);
}

static char *get_toplevel_name(struct expression *expr)
{
        struct symbol *sym;
        char buf[256];

        expr = strip_expr(expr);
        if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->ident)
                return NULL;

        sym = expr->symbol;
        if (!(sym->ctype.modifiers & MOD_TOPLEVEL))
                return NULL;

        if (sym->ctype.modifiers & MOD_STATIC)
                snprintf(buf, sizeof(buf), "%s %s", get_base_file(), sym->ident->name);
        else
                snprintf(buf, sizeof(buf), "extern %s", sym->ident->name);

        return alloc_string(buf);
}

char *get_constraint_str(struct expression *expr)
{
        char *name;

        if (!expr)
                return NULL;
        if (expr->type == EXPR_CALL)
                return get_func_constraint(expr);
        if (expr->type == EXPR_BINOP)
                return expr_to_str(expr);
        name = get_toplevel_name(expr);
        if (name)
                return name;
        return get_member_name(expr);
}

static int save_int_callback(void *_p, int argc, char **argv, char **azColName)
{
        int *p = _p;

        *p = atoi(argv[0]);
        return 0;
}

static int constraint_str_to_id(const char *str)
{
        int id = -1;

        run_sql(save_int_callback, &id,
                "select id from constraints where str = '%q'", str);

        return id;
}

static int save_constraint_str(void *_str, int argc, char **argv, char **azColName)
{
        char **str = _str;

        *str = alloc_string(argv[0]);
        return 0;
}

static char *constraint_id_to_str(int id)
{
        char *str = NULL;

        run_sql(save_constraint_str, &str,
                "select str from constraints where id = '%d'", id);

        return str;
}

static int save_op_callback(void *_p, int argc, char **argv, char **azColName)
{
        int *p = _p;

        if (argv[0][0] == '<' && argv[0][1] == '=')
                *p = SPECIAL_LTE;
        else
                *p = '<';
        return 0;
}

static int save_str_callback(void *_p, int argc, char **argv, char **azColName)
{
        char **p = _p;

        if (!*p) {
                *p = alloc_string(argv[0]);
        } else {
                char buf[256];

                snprintf(buf, sizeof(buf), "%s, %s", *p, argv[0]);
                *p = alloc_string(buf);
        }
        return 0;
}

char *get_required_constraint(const char *data_str)
{
        char *required = NULL;

        run_sql(save_str_callback, &required,
                "select bound from constraints_required where data = '%q'", data_str);

        return required;
}

static int get_required_op(char *data_str, char *con_str)
{
        int op = 0;

        run_sql(save_op_callback, &op,
                "select op from constraints_required where data = '%q' and bound = '%q'", data_str, con_str);

        return op;
}

char *unmet_constraint(struct expression *data, struct expression *offset)
{
        struct smatch_state *state;
        struct constraint_list *list;
        struct constraint *con;
        char *data_str;
        char *required;
        int req_op;

        data_str = get_constraint_str(data);
        if (!data_str)
                return NULL;

        required = get_required_constraint(data_str);
        if (!required)
                goto free_data;

        state = get_state_expr(my_id, offset);
        if (!state)
                goto free_data;
        list = state->data;

        /* check the list of bounds on our index against the list that work */
        FOR_EACH_PTR(list, con) {
                char *con_str;

                con_str = constraint_id_to_str(con->id);
                if (!con_str) {
                        sm_msg("constraint %d not found", con->id);
                        continue;
                }

                req_op = get_required_op(data_str, con_str);
                free_string(con_str);
                if (!req_op)
                        continue;
                if (con->op == '<' || con->op == req_op) {
                        free_string(required);
                        required = NULL;
                        goto free_data;
                }
        } END_FOR_EACH_PTR(con);

free_data:
        free_string(data_str);
        return required;
}

struct string_list *saved_constraints;
static void save_new_constraint(const char *con)
{
        if (list_has_string(saved_constraints, con))
                return;
        insert_string(&saved_constraints, con);
        sql_save_constraint(con);
}

static void handle_comparison(struct expression *left, int op, struct expression *right)
{
        struct constraint_list *constraints;
        struct smatch_state *state;
        char *constraint;
        int constraint_id;
        int orig_op = op;
        sval_t sval;

        /* known values are handled in smatch extra */
        if (get_value(left, &sval) || get_value(right, &sval))
                return;

        if (local_debug)
                sm_msg("COMPARE: %s %s %s", expr_to_str(left), show_special(op), expr_to_str(right));

        constraint = get_constraint_str(right);
        if (!constraint)
                return;
        if (local_debug)
                sm_msg("EXPR: %s CONSTRAINT %s", expr_to_str(right), constraint);
        constraint_id = constraint_str_to_id(constraint);
        if (local_debug)
                sm_msg("CONSTRAINT ID %d", constraint_id);
        if (constraint_id < 0)
                save_new_constraint(constraint);
        free_string(constraint);
        if (constraint_id < 0)
                return;

        constraints = get_constraints(left);
        constraints = clone_constraint_list(constraints);
        op = negate_gt(orig_op);
        add_constraint(&constraints, remove_unsigned_from_comparison(op), constraint_id);
        state = alloc_constraint_state(constraints);

        if (op == orig_op) {
                if (local_debug)
                        sm_msg("SETTING %s true %s", expr_to_str(left), state->name);
                set_true_false_states_expr(my_id, left, state, NULL);
        } else {
                if (local_debug)
                        sm_msg("SETTING %s false %s", expr_to_str(left), state->name);

                set_true_false_states_expr(my_id, left, NULL, state);
        }
}

static void match_condition(struct expression *expr)
{
        if (expr->type != EXPR_COMPARE)
                return;

        if (expr->op == SPECIAL_EQUAL ||
            expr->op == SPECIAL_NOTEQUAL)
                return;

        handle_comparison(expr->left, expr->op, expr->right);
        handle_comparison(expr->right, flip_comparison(expr->op), expr->left);
}

struct constraint_list *get_constraints(struct expression *expr)
{
        struct smatch_state *state;

        state = get_state_expr(my_id, expr);
        if (!state)
                return NULL;
        return state->data;
}

static void match_caller_info(struct expression *expr)
{
        struct expression *tmp;
        struct smatch_state *state;
        int i;

        i = -1;
        FOR_EACH_PTR(expr->args, tmp) {
                i++;
                state = get_state_expr(my_id, tmp);
                if (!state || state == &merged || state == &undefined)
                        continue;
                sql_insert_caller_info(expr, CONSTRAINT, i, "$", state->name);
        } END_FOR_EACH_PTR(tmp);
}

static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
{
        if (sm->state == &merged || sm->state == &undefined)
                return;
        sql_insert_caller_info(call, CONSTRAINT, param, printed_name, sm->state->name);
}

static struct smatch_state *constraint_str_to_state(char *value)
{
        struct constraint_list *list = NULL;
        char *p = value;
        int op;
        long long id;

        while (true) {
                op = '<';
                if (*p != '<')
                        return &undefined;
                p++;
                if (*p == '=') {
                        op = SPECIAL_LTE;
                        p++;
                }
                id = strtoll(p, &p, 10);
                add_constraint(&list, op, id);
                if (*p != ',')
                        break;
                p++;
                if (*p != ' ')
                        return &undefined;
        }

        return alloc_constraint_state(list);
}

static void set_param_constrained(const char *name, struct symbol *sym, char *key, char *value)
{
        char fullname[256];

        if (strcmp(key, "*$") == 0)
                snprintf(fullname, sizeof(fullname), "*%s", name);
        else if (strncmp(key, "$", 1) == 0)
                snprintf(fullname, 256, "%s%s", name, key + 1);
        else
                return;

        set_state(my_id, name, sym, constraint_str_to_state(value));
}

static void print_return_implies_constrained(int return_id, char *return_ranges, struct expression *expr)
{
        struct smatch_state *orig;
        struct sm_state *sm;
        const char *param_name;
        int param;

        FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
                if (sm->state == &merged || sm->state == &undefined)
                        continue;

                param = get_param_num_from_sym(sm->sym);
                if (param < 0)
                        continue;

                orig = get_state_stree(get_start_states(), my_id, sm->name, sm->sym);
                if (orig && strcmp(sm->state->name, orig->name) == 0)
                        continue;

                param_name = get_param_name(sm);
                if (!param_name)
                        continue;

                sql_insert_return_states(return_id, return_ranges, CONSTRAINT,
                                         param, param_name, sm->state->name);
        } END_FOR_EACH_SM(sm);
}

static void db_returns_constrained(struct expression *expr, int param, char *key, char *value)
{
        char *name;
        struct symbol *sym;

        name = return_state_to_var_sym(expr, param, key, &sym);
        if (!name || !sym)
                goto free;

        set_state(my_id, name, sym, constraint_str_to_state(value));
free:
        free_string(name);
}

void register_constraints(int id)
{
        my_id = id;

        add_merge_hook(my_id, &merge_func);
        add_hook(&match_condition, CONDITION_HOOK);

        add_hook(&match_caller_info, FUNCTION_CALL_HOOK);
        add_member_info_callback(my_id, struct_member_callback);
        select_caller_info_hook(&set_param_constrained, CONSTRAINT);

        add_split_return_callback(print_return_implies_constrained);
        select_return_states_hook(CONSTRAINT, &db_returns_constrained);
}