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