smatch_function_hooks.c

   1 /*
   2  * sparse/smatch_function_hooks.c
   3  *
   4  * Copyright (C) 2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * There are three types of function hooks:
  12  * add_function_hook()        - For any time a function is called.
  13  * add_function_assign_hook() - foo = the_function().
  14  * add_conditional_hook()     - For when the return value implies something.
  15  *                              For example a return value of 1 might mean
  16  *                              a lock is held and 0 means it is not held.
  17  * return_implies_state()     - For when a return value of 1 implies locked
  18  *                              and 0 implies unlocked. etc. etc.
  19  *
  20  */
  21
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include "smatch.h"
  25 #include "smatch_slist.h"
  26 #include "smatch_extra.h"
  27 #include "smatch_function_hashtable.h"
  28
  29 struct fcall_back {
  30         int type;
  31         struct data_range *range;
  32         func_hook *call_back;
  33         void *info;
  34 };
  35
  36 ALLOCATOR(fcall_back, "call backs");
  37 DECLARE_PTR_LIST(call_back_list, struct fcall_back);
  38
  39 DEFINE_FUNCTION_HASHTABLE_STATIC(callback, struct fcall_back, struct call_back_list);
  40 static struct hashtable *func_hash;
  41
  42 #define REGULAR_CALL     0
  43 #define CONDITIONAL_CALL 1
  44 #define ASSIGN_CALL      2
  45 #define RANGED_CALL      3
  46
  47 static struct fcall_back *alloc_fcall_back(int type, func_hook *call_back,
  48                                            void *info)
  49 {
  50         struct fcall_back *cb;
  51
  52         cb = __alloc_fcall_back(0);
  53         cb->type = type;
  54         cb->call_back = call_back;
  55         cb->info = info;
  56         return cb;
  57 }
  58
  59 void add_function_hook(const char *look_for, func_hook *call_back, void *info)
  60 {
  61         struct fcall_back *cb;
  62
  63         cb = alloc_fcall_back(REGULAR_CALL, call_back, info);
  64         add_callback(func_hash, look_for, cb);
  65 }
  66
  67 void add_conditional_hook(const char *look_for, func_hook *call_back,
  68                           void *info)
  69 {
  70         struct fcall_back *cb;
  71
  72         cb = alloc_fcall_back(CONDITIONAL_CALL, call_back, info);
  73         add_callback(func_hash, look_for, cb);
  74 }
  75
  76 void add_function_assign_hook(const char *look_for, func_hook *call_back,
  77                               void *info)
  78 {
  79         struct fcall_back *cb;
  80
  81         cb = alloc_fcall_back(ASSIGN_CALL, call_back, info);
  82         add_callback(func_hash, look_for, cb);
  83 }
  84
  85 void return_implies_state(const char *look_for, long long start, long long end,
  86                          implication_hook *call_back, void *info)
  87 {
  88         struct fcall_back *cb;
  89
  90         cb = alloc_fcall_back(RANGED_CALL, (func_hook *)call_back, info);
  91         cb->range = alloc_range_perm(start, end);
  92         add_callback(func_hash, look_for, cb);
  93 }
  94
  95 static void call_call_backs(struct call_back_list *list, int type,
  96                             const char *fn, struct expression *expr)
  97 {
  98         struct fcall_back *tmp;
  99
 100         FOR_EACH_PTR(list, tmp) {
 101                 if (tmp->type == type)
 102                         (tmp->call_back)(fn, expr, tmp->info);
 103         } END_FOR_EACH_PTR(tmp);
 104 }
 105
 106 static void call_ranged_call_backs(struct call_back_list *list,
 107                                 const char *fn, struct expression *call_expr,
 108                                 struct expression *assign_expr)
 109 {
 110         struct fcall_back *tmp;
 111
 112         FOR_EACH_PTR(list, tmp) {
 113                 ((implication_hook *)(tmp->call_back))(fn, call_expr, assign_expr, tmp->info);
 114         } END_FOR_EACH_PTR(tmp);
 115 }
 116
 117 static void match_function_call(struct expression *expr)
 118 {
 119         struct call_back_list *call_backs;
 120
 121         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 122                 return;
 123         call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name);
 124         if (!call_backs)
 125                 return;
 126         call_call_backs(call_backs, REGULAR_CALL, expr->fn->symbol->ident->name,
 127                         expr);
 128 }
 129
 130 static void assign_condition_funcs(const char *fn, struct expression *expr,
 131                                  struct call_back_list *call_backs)
 132 {
 133         struct fcall_back *tmp;
 134         struct sm_state *sm;
 135         int conditional = 0;
 136         char *var_name;
 137         struct symbol *sym;
 138         struct smatch_state *zero_state, *non_zero_state;
 139
 140         var_name = get_variable_from_expr(expr->left, &sym);
 141         if (!var_name || !sym)
 142                 goto free;
 143
 144         __fake_conditions = 1;
 145         FOR_EACH_PTR(call_backs, tmp) {
 146                 if (tmp->type != CONDITIONAL_CALL)
 147                         continue;
 148
 149                 conditional = 1;
 150                 (tmp->call_back)(fn, expr->right, tmp->info);
 151         } END_FOR_EACH_PTR(tmp);
 152         if (conditional) {
 153                 zero_state = alloc_extra_state(0);
 154                 non_zero_state = add_filter(extra_undefined(), 0);
 155                 set_true_false_states(SMATCH_EXTRA, var_name, sym, non_zero_state, zero_state);
 156         }
 157         __fake_conditions = 0;
 158
 159         if (!conditional)
 160                 goto free;
 161
 162         merge_slist(&__fake_cond_true, __fake_cond_false);
 163
 164         FOR_EACH_PTR(__fake_cond_true, sm) {
 165                 __set_state(sm);
 166         } END_FOR_EACH_PTR(sm);
 167         free_slist(&__fake_cond_true);
 168         free_slist(&__fake_cond_false);
 169 free:
 170         free_string(var_name);
 171 }
 172
 173 static struct call_back_list *get_same_ranged_call_backs(struct call_back_list *list,
 174                                                 struct data_range *drange)
 175 {
 176         struct call_back_list *ret = NULL;
 177         struct fcall_back *tmp;
 178
 179         FOR_EACH_PTR(list, tmp) {
 180                 if (tmp->type != RANGED_CALL)
 181                         continue;
 182                 if (tmp->range->min == drange->min && tmp->range->max == drange->max)
 183                         add_ptr_list(&ret, tmp);
 184         } END_FOR_EACH_PTR(tmp);
 185         return ret;
 186 }
 187
 188 static void assign_ranged_funcs(const char *fn, struct expression *expr,
 189                                  struct call_back_list *call_backs)
 190 {
 191         struct fcall_back *tmp;
 192         struct sm_state *sm;
 193         char *var_name;
 194         struct symbol *sym;
 195         struct smatch_state *extra_state;
 196         struct state_list *final_states = NULL;
 197         struct range_list *handled_ranges = NULL;
 198         struct call_back_list *same_range_call_backs = NULL;
 199
 200         var_name = get_variable_from_expr(expr->left, &sym);
 201         if (!var_name || !sym)
 202                 goto free;
 203
 204         __fake_cur = 1;
 205         FOR_EACH_PTR(call_backs, tmp) {
 206                 if (tmp->type != RANGED_CALL)
 207                         continue;
 208                 if (in_list_exact(handled_ranges, tmp->range))
 209                         continue;
 210                 tack_on(&handled_ranges, tmp->range);
 211
 212                 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
 213                 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr);
 214                 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
 215
 216                 extra_state = alloc_extra_state_range(tmp->range->min, tmp->range->max);
 217                 set_state(SMATCH_EXTRA, var_name, sym, extra_state);
 218
 219                 merge_slist(&final_states, __fake_cur_slist);
 220                 free_slist(&__fake_cur_slist);
 221         } END_FOR_EACH_PTR(tmp);
 222         __fake_cur = 0;
 223
 224         FOR_EACH_PTR(final_states, sm) {
 225                 __set_state(sm);
 226         } END_FOR_EACH_PTR(sm);
 227
 228         free_slist(&final_states);
 229 free:
 230         free_string(var_name);
 231 }
 232
 233 void function_comparison(int comparison, struct expression *expr, long long value, int left)
 234 {
 235         struct call_back_list *call_backs;
 236         struct fcall_back *tmp;
 237         const char *fn;
 238         struct data_range *value_range;
 239         struct state_list *true_states = NULL;
 240         struct state_list *false_states = NULL;
 241         struct sm_state *sm;
 242
 243         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 244                 return;
 245         fn = expr->fn->symbol->ident->name;
 246         call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name);
 247         if (!call_backs)
 248                 return;
 249         value_range = alloc_range(value, value);
 250
 251         __fake_cur = 1;
 252         /* set true states */
 253         FOR_EACH_PTR(call_backs, tmp) {
 254                 if (tmp->type != RANGED_CALL)
 255                         continue;
 256                 if (!true_comparison_range_lr(comparison, tmp->range, value_range, left))
 257                         continue;
 258                 ((implication_hook *)(tmp->call_back))(fn, expr, NULL, tmp->info);
 259         } END_FOR_EACH_PTR(tmp);
 260         merge_slist(&true_states, __fake_cur_slist);
 261         free_slist(&__fake_cur_slist);
 262
 263         /* set false states */
 264         FOR_EACH_PTR(call_backs, tmp) {
 265                 if (tmp->type != RANGED_CALL)
 266                         continue;
 267                 if (!false_comparison_range_lr(comparison, tmp->range, value_range, left))
 268                         continue;
 269                 ((implication_hook *)(tmp->call_back))(fn, expr, NULL, tmp->info);
 270         } END_FOR_EACH_PTR(tmp);
 271         merge_slist(&false_states, __fake_cur_slist);
 272         free_slist(&__fake_cur_slist);
 273         __fake_cur = 0;
 274
 275         FOR_EACH_PTR(true_states, sm) {
 276                 __set_true_false_sm(sm, NULL);
 277         } END_FOR_EACH_PTR(sm);
 278         FOR_EACH_PTR(false_states, sm) {
 279                 __set_true_false_sm(NULL, sm);
 280         } END_FOR_EACH_PTR(sm);
 281
 282         if (true_states && !false_states)
 283                 sm_msg("warning:  unhandled false condition.");
 284         if (!true_states && false_states)
 285                 sm_msg("warning:  unhandled true condition.");
 286         free_slist(&true_states);
 287         free_slist(&false_states);
 288 }
 289
 290 static void match_assign_call(struct expression *expr)
 291 {
 292         struct call_back_list *call_backs;
 293         const char *fn;
 294         struct expression *right;
 295
 296         right = strip_expr(expr->right);
 297         if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol)
 298                 return;
 299         fn = right->fn->symbol->ident->name;
 300         call_backs = search_callback(func_hash, (char *)fn);
 301         if (!call_backs)
 302                 return;
 303         call_call_backs(call_backs, ASSIGN_CALL, fn, expr);
 304         assign_condition_funcs(fn, expr, call_backs);
 305         assign_ranged_funcs(fn, expr, call_backs);
 306 }
 307
 308 static void match_conditional_call(struct expression *expr)
 309 {
 310         struct call_back_list *call_backs;
 311         struct fcall_back *tmp;
 312         struct sm_state *sm;
 313         const char *fn;
 314
 315         expr = strip_expr(expr);
 316         if (expr->type != EXPR_CALL)
 317                 return;
 318
 319         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 320                 return;
 321
 322         fn = expr->fn->symbol->ident->name;
 323         call_backs = search_callback(func_hash, (char *)fn);
 324         if (!call_backs)
 325                 return;
 326         __fake_conditions = 1;
 327         FOR_EACH_PTR(call_backs, tmp) {
 328                 if (tmp->type != CONDITIONAL_CALL)
 329                         continue;
 330
 331                 (tmp->call_back)(fn, expr, tmp->info);
 332
 333                 FOR_EACH_PTR(__fake_cond_true, sm) {
 334                         __set_true_false_sm(sm, NULL);
 335                 } END_FOR_EACH_PTR(sm);
 336                 free_slist(&__fake_cond_true);
 337
 338                 FOR_EACH_PTR(__fake_cond_false, sm) {
 339                         __set_true_false_sm(NULL, sm);
 340                 } END_FOR_EACH_PTR(sm);
 341                 free_slist(&__fake_cond_false);
 342
 343         } END_FOR_EACH_PTR(tmp);
 344         __fake_conditions = 0;
 345 }
 346
 347 void create_function_hook_hash(void)
 348 {
 349         func_hash = create_function_hashtable(5000);
 350 }
 351
 352 void register_function_hooks(int id)
 353 {
 354         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 355         add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK);
 356         add_hook(&match_conditional_call, CONDITION_HOOK);
 357 }