sparse.c

   1 /*
   2  * Example trivial client program that uses the sparse library
   3  * to tokenize, pre-process and parse a C file, and prints out
   4  * the results.
   5  *
   6  * Copyright (C) 2003 Transmeta Corp.
   7  *               2003-2004 Linus Torvalds
   8  *
   9  *  Licensed under the Open Software License version 1.1
  10  */
  11 #include <stdarg.h>
  12 #include <stdlib.h>
  13 #include <stdio.h>
  14 #include <string.h>
  15 #include <ctype.h>
  16 #include <unistd.h>
  17 #include <fcntl.h>
  18
  19 #include "lib.h"
  20 #include "allocate.h"
  21 #include "token.h"
  22 #include "parse.h"
  23 #include "symbol.h"
  24 #include "expression.h"
  25 #include "linearize.h"
  26
  27 static int context_increase(struct basic_block *bb, int entry)
  28 {
  29         int sum = 0;
  30         struct instruction *insn;
  31
  32         FOR_EACH_PTR(bb->insns, insn) {
  33                 int val;
  34                 if (insn->opcode != OP_CONTEXT)
  35                         continue;
  36                 val = insn->increment;
  37                 if (insn->check) {
  38                         int current = sum + entry;
  39                         if (!val) {
  40                                 if (!current)
  41                                         continue;
  42                         } else if (current >= val)
  43                                 continue;
  44                         warning(insn->pos, "context check failure");
  45                         continue;
  46                 }
  47                 sum += val;
  48         } END_FOR_EACH_PTR(insn);
  49         return sum;
  50 }
  51
  52 static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
  53 {
  54         if (Wcontext) {
  55                 struct symbol *sym = ep->name;
  56                 warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
  57         }
  58         return -1;
  59 }
  60
  61 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
  62
  63 static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
  64 {
  65         struct instruction *insn;
  66         struct basic_block *child;
  67
  68         insn = last_instruction(bb->insns);
  69         if (!insn)
  70                 return 0;
  71         if (insn->opcode == OP_RET)
  72                 return entry != exit ? imbalance(ep, bb, entry, exit, "wrong count at exit") : 0;
  73
  74         FOR_EACH_PTR(bb->children, child) {
  75                 if (check_bb_context(ep, child, entry, exit))
  76                         return -1;
  77         } END_FOR_EACH_PTR(child);
  78         return 0;
  79 }
  80
  81 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
  82 {
  83         if (!bb)
  84                 return 0;
  85         if (bb->context == entry)
  86                 return 0;
  87
  88         /* Now that's not good.. */
  89         if (bb->context >= 0)
  90                 return imbalance(ep, bb, entry, bb->context, "different lock contexts for basic block");
  91
  92         bb->context = entry;
  93         entry += context_increase(bb, entry);
  94         if (entry < 0)
  95                 return imbalance(ep, bb, entry, exit, "unexpected unlock");
  96
  97         return check_children(ep, bb, entry, exit);
  98 }
  99
 100 static void check_cast_instruction(struct instruction *insn)
 101 {
 102         struct symbol *orig_type = insn->orig_type;
 103         if (orig_type) {
 104                 int old = orig_type->bit_size;
 105                 int new = insn->size;
 106                 int oldsigned = (orig_type->ctype.modifiers & MOD_SIGNED) != 0;
 107                 int newsigned = insn->opcode == OP_SCAST;
 108
 109                 if (new > old) {
 110                         if (oldsigned == newsigned)
 111                                 return;
 112                         if (newsigned)
 113                                 return;
 114                         warning(insn->pos, "cast loses sign");
 115                         return;
 116                 }
 117                 if (new < old) {
 118                         warning(insn->pos, "cast drops bits");
 119                         return;
 120                 }
 121                 if (oldsigned == newsigned) {
 122                         warning(insn->pos, "cast wasn't removed");
 123                         return;
 124                 }
 125                 warning(insn->pos, "cast changes sign");
 126         }
 127 }
 128
 129 static void check_range_instruction(struct instruction *insn)
 130 {
 131         warning(insn->pos, "value out of range");
 132 }
 133
 134 static void check_byte_count(struct instruction *insn, pseudo_t count)
 135 {
 136         if (!count)
 137                 return;
 138         if (count->type == PSEUDO_VAL) {
 139                 long long val = count->value;
 140                 if (val <= 0 || val > 100000)
 141                         warning(insn->pos, "%s with byte count of %lld",
 142                                 show_ident(insn->func->sym->ident), val);
 143                 return;
 144         }
 145         /* Ok, we could try to do the range analysis here */
 146 }
 147
 148 static pseudo_t argument(struct instruction *call, unsigned int argno)
 149 {
 150         pseudo_t args[8];
 151         struct ptr_list *arg_list = (struct ptr_list *) call->arguments;
 152
 153         argno--;
 154         if (linearize_ptr_list(arg_list, (void *)args, 8) > argno)
 155                 return args[argno];
 156         return NULL;
 157 }
 158
 159 static void check_memset(struct instruction *insn)
 160 {
 161         check_byte_count(insn, argument(insn, 3));
 162 }
 163
 164 #define check_memcpy check_memset
 165 #define check_ctu check_memset
 166 #define check_cfu check_memset
 167
 168 struct checkfn {
 169         struct ident *id;
 170         void (*check)(struct instruction *insn);
 171 };
 172
 173 static void check_call_instruction(struct instruction *insn)
 174 {
 175         pseudo_t fn = insn->func;
 176         struct ident *ident;
 177         static const struct checkfn check_fn[] = {
 178                 { &memset_ident, check_memset },
 179                 { &memcpy_ident, check_memcpy },
 180                 { &copy_to_user_ident, check_ctu },
 181                 { &copy_from_user_ident, check_cfu },
 182         };
 183         int i;
 184
 185         if (fn->type != PSEUDO_SYM)
 186                 return;
 187         ident = fn->sym->ident;
 188         if (!ident)
 189                 return;
 190         for (i = 0; i < sizeof(check_fn)/sizeof(struct checkfn) ; i++) {
 191                 if (check_fn[i].id != ident)
 192                         continue;
 193                 check_fn[i].check(insn);
 194                 break;
 195         }
 196 }
 197
 198 static void check_one_instruction(struct instruction *insn)
 199 {
 200         switch (insn->opcode) {
 201         case OP_CAST: case OP_SCAST:
 202                 if (verbose)
 203                         check_cast_instruction(insn);
 204                 break;
 205         case OP_RANGE:
 206                 check_range_instruction(insn);
 207                 break;
 208         case OP_CALL:
 209                 check_call_instruction(insn);
 210                 break;
 211         default:
 212                 break;
 213         }
 214 }
 215
 216 static void check_bb_instructions(struct basic_block *bb)
 217 {
 218         struct instruction *insn;
 219         FOR_EACH_PTR(bb->insns, insn) {
 220                 if (!insn->bb)
 221                         continue;
 222                 check_one_instruction(insn);
 223         } END_FOR_EACH_PTR(insn);
 224 }
 225
 226 static void check_instructions(struct entrypoint *ep)
 227 {
 228         struct basic_block *bb;
 229         FOR_EACH_PTR(ep->bbs, bb) {
 230                 check_bb_instructions(bb);
 231         } END_FOR_EACH_PTR(bb);
 232 }
 233
 234 static void check_context(struct entrypoint *ep)
 235 {
 236         struct symbol *sym = ep->name;
 237         struct context *context;
 238         unsigned int in_context = 0, out_context = 0;
 239
 240         if (Wuninitialized && verbose && ep->entry->bb->needs) {
 241                 pseudo_t pseudo;
 242                 FOR_EACH_PTR(ep->entry->bb->needs, pseudo) {
 243                         if (pseudo->type != PSEUDO_ARG)
 244                                 warning(sym->pos, "%s: possible uninitialized variable (%s)",
 245                                         show_ident(sym->ident), show_pseudo(pseudo));
 246                 } END_FOR_EACH_PTR(pseudo);
 247         }
 248
 249         check_instructions(ep);
 250
 251         FOR_EACH_PTR(sym->ctype.contexts, context) {
 252                 in_context += context->in;
 253                 out_context += context->out;
 254         } END_FOR_EACH_PTR(context);
 255         check_bb_context(ep, ep->entry->bb, in_context, out_context);
 256 }
 257
 258 static void check_symbols(struct symbol_list *list)
 259 {
 260         struct symbol *sym;
 261
 262         FOR_EACH_PTR(list, sym) {
 263                 struct entrypoint *ep;
 264
 265                 expand_symbol(sym);
 266                 ep = linearize_symbol(sym);
 267                 if (ep) {
 268                         if (dbg_entry)
 269                                 show_entry(ep);
 270
 271                         check_context(ep);
 272                 }
 273         } END_FOR_EACH_PTR(sym);
 274 }
 275
 276 int main(int argc, char **argv)
 277 {
 278         struct string_list *filelist = NULL;
 279         char *file;
 280
 281         // Expand, linearize and show it.
 282         check_symbols(sparse_initialize(argc, argv, &filelist));
 283         FOR_EACH_PTR_NOTAG(filelist, file) {
 284                 check_symbols(sparse(file));
 285         } END_FOR_EACH_PTR_NOTAG(file);
 286         return 0;
 287 }