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->type != RANGED_CALL)
 214                         continue;
 215                 if (tmp->range->min == drange->min && tmp->range->max == drange->max)
 216                         add_ptr_list(&ret, tmp);
 217         } END_FOR_EACH_PTR(tmp);
 218         return ret;
 219 }
 220
 221 static void assign_ranged_funcs(const char *fn, struct expression *expr,
 222                                  struct call_back_list *call_backs)
 223 {
 224         struct fcall_back *tmp;
 225         struct sm_state *sm;
 226         char *var_name;
 227         struct symbol *sym;
 228         struct smatch_state *extra_state;
 229         struct state_list *final_states = NULL;
 230         struct range_list *handled_ranges = NULL;
 231         struct call_back_list *same_range_call_backs = NULL;
 232
 233         var_name = get_variable_from_expr(expr->left, &sym);
 234         if (!var_name || !sym)
 235                 goto free;
 236
 237         __fake_cur = 1;
 238         FOR_EACH_PTR(call_backs, tmp) {
 239                 if (tmp->type != RANGED_CALL)
 240                         continue;
 241                 if (in_list_exact(handled_ranges, tmp->range))
 242                         continue;
 243                 tack_on(&handled_ranges, tmp->range);
 244
 245                 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
 246                 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr);
 247                 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
 248
 249                 extra_state = alloc_extra_state_range(tmp->range->min, tmp->range->max);
 250                 set_state(SMATCH_EXTRA, var_name, sym, extra_state);
 251
 252                 merge_slist(&final_states, __fake_cur_slist);
 253                 free_slist(&__fake_cur_slist);
 254         } END_FOR_EACH_PTR(tmp);
 255         __fake_cur = 0;
 256
 257         FOR_EACH_PTR(final_states, sm) {
 258                 __set_state(sm);
 259         } END_FOR_EACH_PTR(sm);
 260
 261         free_slist(&final_states);
 262 free:
 263         free_string(var_name);
 264 }
 265
 266 void function_comparison(int comparison, struct expression *expr, long long value, int left)
 267 {
 268         struct call_back_list *call_backs;
 269         struct fcall_back *tmp;
 270         const char *fn;
 271         struct data_range *value_range;
 272         struct state_list *true_states = NULL;
 273         struct state_list *false_states = NULL;
 274         struct sm_state *sm;
 275
 276         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 277                 return;
 278         fn = expr->fn->symbol->ident->name;
 279         call_backs = get_call_backs(expr->fn->symbol->ident->name);
 280         if (!call_backs)
 281                 return;
 282         value_range = alloc_range(value, value);
 283
 284         __fake_cur = 1;
 285         /* set true states */
 286         FOR_EACH_PTR(call_backs, tmp) {
 287                 if (tmp->type != RANGED_CALL)
 288                         continue;
 289                 if (!true_comparison_range_lr(comparison, tmp->range, value_range, left))
 290                         continue;
 291                 ((implication_hook *)(tmp->call_back))(fn, expr, NULL, tmp->info);
 292                 merge_slist(&true_states, __fake_cur_slist);
 293                 free_slist(&__fake_cur_slist);
 294         } END_FOR_EACH_PTR(tmp);
 295
 296         /* set false states */
 297         FOR_EACH_PTR(call_backs, tmp) {
 298                 if (tmp->type != RANGED_CALL)
 299                         continue;
 300                 if (!false_comparison_range_lr(comparison, tmp->range, value_range, left))
 301                         continue;
 302                 ((implication_hook *)(tmp->call_back))(fn, expr, NULL, tmp->info);
 303                 merge_slist(&false_states, __fake_cur_slist);
 304                 free_slist(&__fake_cur_slist);
 305         } END_FOR_EACH_PTR(tmp);
 306         __fake_cur = 0;
 307
 308         FOR_EACH_PTR(true_states, sm) {
 309                 __set_true_false_sm(sm, NULL);
 310         } END_FOR_EACH_PTR(sm);
 311         FOR_EACH_PTR(false_states, sm) {
 312                 __set_true_false_sm(NULL, sm);
 313         } END_FOR_EACH_PTR(sm);
 314
 315         if (true_states && !false_states)
 316                 sm_msg("warning:  unhandled false condition.");
 317         if (!true_states && false_states)
 318                 sm_msg("warning:  unhandled true condition.");
 319         free_slist(&true_states);
 320         free_slist(&false_states);
 321 }
 322
 323 static void match_assign_call(struct expression *expr)
 324 {
 325         struct call_back_list *call_backs;
 326         const char *fn;
 327         struct expression *right;
 328
 329         right = strip_expr(expr->right);
 330         if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol)
 331                 return;
 332         fn = right->fn->symbol->ident->name;
 333         call_backs = get_call_backs(fn);
 334         if (!call_backs)
 335                 return;
 336         call_call_backs(call_backs, ASSIGN_CALL, fn, expr);
 337         assign_condition_funcs(fn, expr, call_backs);
 338         assign_ranged_funcs(fn, expr, call_backs);
 339 }
 340
 341 static void match_conditional_call(struct expression *expr)
 342 {
 343         struct call_back_list *call_backs;
 344         struct fcall_back *tmp;
 345         struct sm_state *sm;
 346         const char *fn;
 347
 348         expr = strip_expr(expr);
 349         if (expr->type != EXPR_CALL)
 350                 return;
 351
 352         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 353                 return;
 354
 355         fn = expr->fn->symbol->ident->name;
 356         call_backs = get_call_backs(fn);
 357         if (!call_backs)
 358                 return;
 359         __fake_conditions = 1;
 360         FOR_EACH_PTR(call_backs, tmp) {
 361                 if (tmp->type != CONDITIONAL_CALL)
 362                         continue;
 363
 364                 (tmp->call_back)(fn, expr, tmp->info);
 365
 366                 FOR_EACH_PTR(__fake_cond_true, sm) {
 367                         __set_true_false_sm(sm, NULL);
 368                 } END_FOR_EACH_PTR(sm);
 369                 free_slist(&__fake_cond_true);
 370
 371                 FOR_EACH_PTR(__fake_cond_false, sm) {
 372                         __set_true_false_sm(NULL, sm);
 373                 } END_FOR_EACH_PTR(sm);
 374                 free_slist(&__fake_cond_false);
 375
 376         } END_FOR_EACH_PTR(tmp);
 377         __fake_conditions = 0;
 378 }
 379
 380 void create_function_hash(void)
 381 {
 382         hcreate_r(10000, &func_hash);  // Apparently 1000 is too few...
 383 }
 384
 385 void register_function_hooks(int id)
 386 {
 387         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 388         add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK);
 389         add_hook(&match_conditional_call, CONDITION_HOOK);
 390 }