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                          func_hook *call_back, void *info)
 120 {
 121         struct fcall_back *cb;
 122
 123         cb = alloc_fcall_back(RANGED_CALL, 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 match_function_call(struct expression *expr)
 140 {
 141         struct call_back_list *call_backs;
 142
 143         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 144                 return;
 145         call_backs = get_call_backs(expr->fn->symbol->ident->name);
 146         if (!call_backs)
 147                 return;
 148         call_call_backs(call_backs, REGULAR_CALL, expr->fn->symbol->ident->name,
 149                         expr);
 150 }
 151
 152 static void assign_condition_funcs(const char *fn, struct expression *expr,
 153                                  struct call_back_list *call_backs)
 154 {
 155         struct fcall_back *tmp;
 156         struct sm_state *sm;
 157         int conditional = 0;
 158         char *var_name;
 159         struct symbol *sym;
 160         struct smatch_state *zero_state, *non_zero_state;
 161
 162         var_name = get_variable_from_expr(expr->left, &sym);
 163         if (!var_name || !sym)
 164                 goto free;
 165
 166         __fake_conditions = 1;
 167         FOR_EACH_PTR(call_backs, tmp) {
 168                 if (tmp->type != CONDITIONAL_CALL)
 169                         continue;
 170
 171                 conditional = 1;
 172                 (tmp->call_back)(fn, expr->right, tmp->info);
 173         } END_FOR_EACH_PTR(tmp);
 174         if (conditional) {
 175                 zero_state = alloc_extra_state(0);
 176                 non_zero_state = add_filter(extra_undefined(), 0);
 177                 set_true_false_states(SMATCH_EXTRA, var_name, sym, non_zero_state, zero_state);
 178         }
 179         __fake_conditions = 0;
 180
 181         if (!conditional)
 182                 goto free;
 183
 184         merge_slist(&__fake_cond_true, __fake_cond_false);
 185
 186         FOR_EACH_PTR(__fake_cond_true, sm) {
 187                 __set_state(sm);
 188         } END_FOR_EACH_PTR(sm);
 189         free_slist(&__fake_cond_true);
 190         free_slist(&__fake_cond_false);
 191 free:
 192         free_string(var_name);
 193 }
 194
 195 static struct call_back_list *get_same_ranged_call_backs(struct call_back_list *list,
 196                                                 struct data_range *drange)
 197 {
 198         struct call_back_list *ret = NULL;
 199         struct fcall_back *tmp;
 200
 201         FOR_EACH_PTR(list, tmp) {
 202                 if (tmp->range->min == drange->min && tmp->range->max == drange->max)
 203                         add_ptr_list(&ret, tmp);
 204         } END_FOR_EACH_PTR(tmp);
 205         return ret;
 206 }
 207
 208 static void assign_ranged_funcs(const char *fn, struct expression *expr,
 209                                  struct call_back_list *call_backs)
 210 {
 211         struct fcall_back *tmp;
 212         struct sm_state *sm;
 213         char *var_name;
 214         struct symbol *sym;
 215         struct smatch_state *extra_state;
 216         struct state_list *final_states = NULL;
 217         struct range_list *handled_ranges = NULL;
 218         struct call_back_list *same_range_call_backs = NULL;
 219
 220         var_name = get_variable_from_expr(expr->left, &sym);
 221         if (!var_name || !sym)
 222                 goto free;
 223
 224         __fake_cur = 1;
 225         FOR_EACH_PTR(call_backs, tmp) {
 226                 if (tmp->type != RANGED_CALL)
 227                         continue;
 228                 if (in_list_exact(handled_ranges, tmp->range))
 229                         continue;
 230                 tack_on(&handled_ranges, tmp->range);
 231
 232                 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
 233                 call_call_backs(same_range_call_backs, RANGED_CALL, fn, expr->right);
 234                 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
 235
 236                 extra_state = alloc_extra_state_range(tmp->range->min, tmp->range->max);
 237                 set_state(SMATCH_EXTRA, var_name, sym, extra_state);
 238
 239                 merge_slist(&final_states, __fake_cur_slist);
 240                 free_slist(&__fake_cur_slist);
 241         } END_FOR_EACH_PTR(tmp);
 242         __fake_cur = 0;
 243
 244         FOR_EACH_PTR(final_states, sm) {
 245                 __set_state(sm);
 246         } END_FOR_EACH_PTR(sm);
 247
 248         free_slist(&final_states);
 249 free:
 250         free_string(var_name);
 251 }
 252
 253 void function_comparison(int comparison, struct expression *expr, long long value, int left)
 254 {
 255         struct call_back_list *call_backs;
 256         struct fcall_back *tmp;
 257         const char *fn;
 258         struct data_range *value_range;
 259         struct state_list *true_states = NULL;
 260         struct state_list *false_states = NULL;
 261         struct sm_state *sm;
 262
 263         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 264                 return;
 265         fn = expr->fn->symbol->ident->name;
 266         call_backs = get_call_backs(expr->fn->symbol->ident->name);
 267         if (!call_backs)
 268                 return;
 269         value_range = alloc_range(value, value);
 270
 271         __fake_cur = 1;
 272         /* set true states */
 273         FOR_EACH_PTR(call_backs, tmp) {
 274                 if (tmp->type != RANGED_CALL)
 275                         continue;
 276                 if (!true_comparison_range_lr(comparison, tmp->range, value_range, left))
 277                         continue;
 278                 (tmp->call_back)(fn, expr, tmp->info);
 279                 merge_slist(&true_states, __fake_cur_slist);
 280                 free_slist(&__fake_cur_slist);
 281         } END_FOR_EACH_PTR(tmp);
 282
 283         /* set false states */
 284         FOR_EACH_PTR(call_backs, tmp) {
 285                 if (tmp->type != RANGED_CALL)
 286                         continue;
 287                 if (!false_comparison_range_lr(comparison, tmp->range, value_range, left))
 288                         continue;
 289                 (tmp->call_back)(fn, expr, tmp->info);
 290                 merge_slist(&false_states, __fake_cur_slist);
 291                 free_slist(&__fake_cur_slist);
 292         } END_FOR_EACH_PTR(tmp);
 293         __fake_cur = 0;
 294
 295         FOR_EACH_PTR(true_states, sm) {
 296                 __set_true_false_sm(sm, NULL);
 297         } END_FOR_EACH_PTR(sm);
 298         FOR_EACH_PTR(false_states, sm) {
 299                 __set_true_false_sm(NULL, sm);
 300         } END_FOR_EACH_PTR(sm);
 301
 302         if (true_states && !false_states)
 303                 sm_msg("warning:  unhandled false condition.");
 304         if (!true_states && false_states)
 305                 sm_msg("warning:  unhandled true condition.");
 306         free_slist(&true_states);
 307         free_slist(&false_states);
 308 }
 309
 310 void __match_initializer_call(struct symbol *sym)
 311 {
 312         struct call_back_list *call_backs;
 313         struct expression *initializer = sym->initializer;
 314         struct expression *e_assign, *e_symbol;
 315         const char *fn;
 316
 317         if (initializer->fn->type != EXPR_SYMBOL
 318             || !initializer->fn->symbol)
 319                 return;
 320         fn = initializer->fn->symbol->ident->name;
 321         call_backs = get_call_backs(fn);
 322         if (!call_backs)
 323                 return;
 324
 325         e_assign = alloc_expression(initializer->pos, EXPR_ASSIGNMENT);
 326         e_symbol = alloc_expression(initializer->pos, EXPR_SYMBOL);
 327         e_symbol->symbol = sym;
 328         e_symbol->symbol_name = sym->ident;
 329         e_assign->left = e_symbol;
 330         e_assign->right = initializer;
 331         call_call_backs(call_backs, ASSIGN_CALL, fn, e_assign);
 332         assign_condition_funcs(fn, e_assign, call_backs);
 333         assign_ranged_funcs(fn, e_assign, call_backs);
 334 }
 335
 336 static void match_assign_call(struct expression *expr)
 337 {
 338         struct call_back_list *call_backs;
 339         const char *fn;
 340         struct expression *right;
 341
 342         right = strip_expr(expr->right);
 343         if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol)
 344                 return;
 345         fn = right->fn->symbol->ident->name;
 346         call_backs = get_call_backs(fn);
 347         if (!call_backs)
 348                 return;
 349         call_call_backs(call_backs, ASSIGN_CALL, fn, expr);
 350         assign_condition_funcs(fn, expr, call_backs);
 351         assign_ranged_funcs(fn, expr, call_backs);
 352 }
 353
 354 static void match_conditional_call(struct expression *expr)
 355 {
 356         struct call_back_list *call_backs;
 357         struct fcall_back *tmp;
 358         struct sm_state *sm;
 359         const char *fn;
 360
 361         expr = strip_expr(expr);
 362         if (expr->type != EXPR_CALL)
 363                 return;
 364
 365         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 366                 return;
 367
 368         fn = expr->fn->symbol->ident->name;
 369         call_backs = get_call_backs(fn);
 370         if (!call_backs)
 371                 return;
 372         __fake_conditions = 1;
 373         FOR_EACH_PTR(call_backs, tmp) {
 374                 if (tmp->type != CONDITIONAL_CALL)
 375                         continue;
 376
 377                 (tmp->call_back)(fn, expr, tmp->info);
 378
 379                 FOR_EACH_PTR(__fake_cond_true, sm) {
 380                         __set_true_false_sm(sm, NULL);
 381                 } END_FOR_EACH_PTR(sm);
 382                 free_slist(&__fake_cond_true);
 383
 384                 FOR_EACH_PTR(__fake_cond_false, sm) {
 385                         __set_true_false_sm(NULL, sm);
 386                 } END_FOR_EACH_PTR(sm);
 387                 free_slist(&__fake_cond_false);
 388
 389         } END_FOR_EACH_PTR(tmp);
 390         __fake_conditions = 0;
 391 }
 392
 393 void create_function_hash(void)
 394 {
 395         hcreate_r(10000, &func_hash);  // Apparently 1000 is too few...
 396 }
 397
 398 void register_function_hooks(int id)
 399 {
 400         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 401         add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK);
 402         add_hook(&match_conditional_call, CONDITION_HOOK);
 403 }