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 #define _GNU_SOURCE
  23 #include <search.h>
  24 #include <stdlib.h>
  25 #include <stdio.h>
  26 #include "smatch.h"
  27 #include "smatch_slist.h"
  28 #include "smatch_extra.h"
  29
  30 struct fcall_back {
  31         int type;
  32         struct data_range *range;
  33         func_hook *call_back;
  34         void *info;
  35 };
  36
  37 ALLOCATOR(fcall_back, "call backs");
  38 DECLARE_PTR_LIST(call_back_list, struct fcall_back);
  39
  40 static struct hsearch_data 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 static struct call_back_list *get_call_backs(const char *look_for)
  60 {
  61         ENTRY e, *ep;
  62
  63         e.key = (char *)look_for;
  64         hsearch_r(e, FIND, &ep, &func_hash);
  65         if (!ep)
  66                 return NULL;
  67         return (struct call_back_list *)ep->data;
  68 }
  69
  70 static void add_cb_hook(const char *look_for, struct fcall_back *cb)
  71 {
  72         ENTRY e, *ep;
  73         char *old_key = NULL;
  74
  75         e.key = alloc_string(look_for);
  76         hsearch_r(e, FIND, &ep, &func_hash);
  77         if (!ep) {
  78                 struct call_back_list *list = NULL;
  79
  80                 add_ptr_list(&list, cb);
  81                 e.data = list;
  82         } else {
  83                 old_key = e.key;
  84                 e.key = ep->key;
  85                 add_ptr_list((struct call_back_list **)&ep->data, cb);
  86                 e.data = ep->data;
  87         }
  88         if (!hsearch_r(e, ENTER, &ep, &func_hash)) {
  89                 printf("Error hash table too small in smatch_function_hooks.c\n");
  90                 exit(1);
  91         }
  92         free_string(old_key);
  93 }
  94
  95 void add_function_hook(const char *look_for, func_hook *call_back, void *info)
  96 {
  97         struct fcall_back *cb;
  98
  99         cb = alloc_fcall_back(REGULAR_CALL, call_back, info);
 100         add_cb_hook(look_for, cb);
 101 }
 102
 103 void add_conditional_hook(const char *look_for, func_hook *call_back,
 104                           void *info)
 105 {
 106         struct fcall_back *cb;
 107
 108         cb = alloc_fcall_back(CONDITIONAL_CALL, call_back, info);
 109         add_cb_hook(look_for, cb);
 110 }
 111
 112 void add_function_assign_hook(const char *look_for, func_hook *call_back,
 113                               void *info)
 114 {
 115         struct fcall_back *cb;
 116
 117         cb = alloc_fcall_back(ASSIGN_CALL, call_back, info);
 118         add_cb_hook(look_for, cb);
 119 }
 120
 121 void return_implies_state(const char *look_for, long long start, long long end,
 122                          implication_hook *call_back, void *info)
 123 {
 124         struct fcall_back *cb;
 125
 126         cb = alloc_fcall_back(RANGED_CALL, (func_hook *)call_back, info);
 127         cb->range = alloc_range_perm(start, end);
 128         add_cb_hook(look_for, cb);
 129 }
 130
 131 static void call_call_backs(struct call_back_list *list, int type,
 132                             const char *fn, struct expression *expr)
 133 {
 134         struct fcall_back *tmp;
 135
 136         FOR_EACH_PTR(list, tmp) {
 137                 if (tmp->type == type)
 138                         (tmp->call_back)(fn, expr, tmp->info);
 139         } END_FOR_EACH_PTR(tmp);
 140 }
 141
 142 static void call_ranged_call_backs(struct call_back_list *list,
 143                                 const char *fn, struct expression *call_expr,
 144                                 struct expression *assign_expr)
 145 {
 146         struct fcall_back *tmp;
 147
 148         FOR_EACH_PTR(list, tmp) {
 149                 ((implication_hook *)(tmp->call_back))(fn, call_expr, assign_expr, tmp->info);
 150         } END_FOR_EACH_PTR(tmp);
 151 }
 152
 153 static void match_function_call(struct expression *expr)
 154 {
 155         struct call_back_list *call_backs;
 156
 157         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 158                 return;
 159         call_backs = get_call_backs(expr->fn->symbol->ident->name);
 160         if (!call_backs)
 161                 return;
 162         call_call_backs(call_backs, REGULAR_CALL, expr->fn->symbol->ident->name,
 163                         expr);
 164 }
 165
 166 static void assign_condition_funcs(const char *fn, struct expression *expr,
 167                                  struct call_back_list *call_backs)
 168 {
 169         struct fcall_back *tmp;
 170         struct sm_state *sm;
 171         int conditional = 0;
 172         char *var_name;
 173         struct symbol *sym;
 174         struct smatch_state *zero_state, *non_zero_state;
 175
 176         var_name = get_variable_from_expr(expr->left, &sym);
 177         if (!var_name || !sym)
 178                 goto free;
 179
 180         __fake_conditions = 1;
 181         FOR_EACH_PTR(call_backs, tmp) {
 182                 if (tmp->type != CONDITIONAL_CALL)
 183                         continue;
 184
 185                 conditional = 1;
 186                 (tmp->call_back)(fn, expr->right, tmp->info);
 187         } END_FOR_EACH_PTR(tmp);
 188         if (conditional) {
 189                 zero_state = alloc_extra_state(0);
 190                 non_zero_state = add_filter(extra_undefined(), 0);
 191                 set_true_false_states(SMATCH_EXTRA, var_name, sym, non_zero_state, zero_state);
 192         }
 193         __fake_conditions = 0;
 194
 195         if (!conditional)
 196                 goto free;
 197
 198         merge_slist(&__fake_cond_true, __fake_cond_false);
 199
 200         FOR_EACH_PTR(__fake_cond_true, sm) {
 201                 __set_state(sm);
 202         } END_FOR_EACH_PTR(sm);
 203         free_slist(&__fake_cond_true);
 204         free_slist(&__fake_cond_false);
 205 free:
 206         free_string(var_name);
 207 }
 208
 209 static struct call_back_list *get_same_ranged_call_backs(struct call_back_list *list,
 210                                                 struct data_range *drange)
 211 {
 212         struct call_back_list *ret = NULL;
 213         struct fcall_back *tmp;
 214
 215         FOR_EACH_PTR(list, tmp) {
 216                 if (tmp->type != RANGED_CALL)
 217                         continue;
 218                 if (tmp->range->min == drange->min && tmp->range->max == drange->max)
 219                         add_ptr_list(&ret, tmp);
 220         } END_FOR_EACH_PTR(tmp);
 221         return ret;
 222 }
 223
 224 static void assign_ranged_funcs(const char *fn, struct expression *expr,
 225                                  struct call_back_list *call_backs)
 226 {
 227         struct fcall_back *tmp;
 228         struct sm_state *sm;
 229         char *var_name;
 230         struct symbol *sym;
 231         struct smatch_state *extra_state;
 232         struct state_list *final_states = NULL;
 233         struct range_list *handled_ranges = NULL;
 234         struct call_back_list *same_range_call_backs = NULL;
 235
 236         var_name = get_variable_from_expr(expr->left, &sym);
 237         if (!var_name || !sym)
 238                 goto free;
 239
 240         __fake_cur = 1;
 241         FOR_EACH_PTR(call_backs, tmp) {
 242                 if (tmp->type != RANGED_CALL)
 243                         continue;
 244                 if (in_list_exact(handled_ranges, tmp->range))
 245                         continue;
 246                 tack_on(&handled_ranges, tmp->range);
 247
 248                 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
 249                 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr);
 250                 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
 251
 252                 extra_state = alloc_extra_state_range(tmp->range->min, tmp->range->max);
 253                 set_state(SMATCH_EXTRA, var_name, sym, extra_state);
 254
 255                 merge_slist(&final_states, __fake_cur_slist);
 256                 free_slist(&__fake_cur_slist);
 257         } END_FOR_EACH_PTR(tmp);
 258         __fake_cur = 0;
 259
 260         FOR_EACH_PTR(final_states, sm) {
 261                 __set_state(sm);
 262         } END_FOR_EACH_PTR(sm);
 263
 264         free_slist(&final_states);
 265 free:
 266         free_string(var_name);
 267 }
 268
 269 void function_comparison(int comparison, struct expression *expr, long long value, int left)
 270 {
 271         struct call_back_list *call_backs;
 272         struct fcall_back *tmp;
 273         const char *fn;
 274         struct data_range *value_range;
 275         struct state_list *true_states = NULL;
 276         struct state_list *false_states = NULL;
 277         struct sm_state *sm;
 278
 279         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 280                 return;
 281         fn = expr->fn->symbol->ident->name;
 282         call_backs = get_call_backs(expr->fn->symbol->ident->name);
 283         if (!call_backs)
 284                 return;
 285         value_range = alloc_range(value, value);
 286
 287         __fake_cur = 1;
 288         /* set true states */
 289         FOR_EACH_PTR(call_backs, tmp) {
 290                 if (tmp->type != RANGED_CALL)
 291                         continue;
 292                 if (!true_comparison_range_lr(comparison, tmp->range, value_range, left))
 293                         continue;
 294                 ((implication_hook *)(tmp->call_back))(fn, expr, NULL, tmp->info);
 295                 merge_slist(&true_states, __fake_cur_slist);
 296                 free_slist(&__fake_cur_slist);
 297         } END_FOR_EACH_PTR(tmp);
 298
 299         /* set false states */
 300         FOR_EACH_PTR(call_backs, tmp) {
 301                 if (tmp->type != RANGED_CALL)
 302                         continue;
 303                 if (!false_comparison_range_lr(comparison, tmp->range, value_range, left))
 304                         continue;
 305                 ((implication_hook *)(tmp->call_back))(fn, expr, NULL, tmp->info);
 306                 merge_slist(&false_states, __fake_cur_slist);
 307                 free_slist(&__fake_cur_slist);
 308         } END_FOR_EACH_PTR(tmp);
 309         __fake_cur = 0;
 310
 311         FOR_EACH_PTR(true_states, sm) {
 312                 __set_true_false_sm(sm, NULL);
 313         } END_FOR_EACH_PTR(sm);
 314         FOR_EACH_PTR(false_states, sm) {
 315                 __set_true_false_sm(NULL, sm);
 316         } END_FOR_EACH_PTR(sm);
 317
 318         if (true_states && !false_states)
 319                 sm_msg("warning:  unhandled false condition.");
 320         if (!true_states && false_states)
 321                 sm_msg("warning:  unhandled true condition.");
 322         free_slist(&true_states);
 323         free_slist(&false_states);
 324 }
 325
 326 static void match_assign_call(struct expression *expr)
 327 {
 328         struct call_back_list *call_backs;
 329         const char *fn;
 330         struct expression *right;
 331
 332         right = strip_expr(expr->right);
 333         if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol)
 334                 return;
 335         fn = right->fn->symbol->ident->name;
 336         call_backs = get_call_backs(fn);
 337         if (!call_backs)
 338                 return;
 339         call_call_backs(call_backs, ASSIGN_CALL, fn, expr);
 340         assign_condition_funcs(fn, expr, call_backs);
 341         assign_ranged_funcs(fn, expr, call_backs);
 342 }
 343
 344 static void match_conditional_call(struct expression *expr)
 345 {
 346         struct call_back_list *call_backs;
 347         struct fcall_back *tmp;
 348         struct sm_state *sm;
 349         const char *fn;
 350
 351         expr = strip_expr(expr);
 352         if (expr->type != EXPR_CALL)
 353                 return;
 354
 355         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 356                 return;
 357
 358         fn = expr->fn->symbol->ident->name;
 359         call_backs = get_call_backs(fn);
 360         if (!call_backs)
 361                 return;
 362         __fake_conditions = 1;
 363         FOR_EACH_PTR(call_backs, tmp) {
 364                 if (tmp->type != CONDITIONAL_CALL)
 365                         continue;
 366
 367                 (tmp->call_back)(fn, expr, tmp->info);
 368
 369                 FOR_EACH_PTR(__fake_cond_true, sm) {
 370                         __set_true_false_sm(sm, NULL);
 371                 } END_FOR_EACH_PTR(sm);
 372                 free_slist(&__fake_cond_true);
 373
 374                 FOR_EACH_PTR(__fake_cond_false, sm) {
 375                         __set_true_false_sm(NULL, sm);
 376                 } END_FOR_EACH_PTR(sm);
 377                 free_slist(&__fake_cond_false);
 378
 379         } END_FOR_EACH_PTR(tmp);
 380         __fake_conditions = 0;
 381 }
 382
 383 void create_function_hash(void)
 384 {
 385         hcreate_r(10000, &func_hash);  // Apparently 1000 is too few...
 386 }
 387
 388 void register_function_hooks(int id)
 389 {
 390         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 391         add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK);
 392         add_hook(&match_conditional_call, CONDITION_HOOK);
 393 }