sparse.c

   1 /*
   2  * Example trivial client program that uses the sparse library
   3  * to tokenize, preprocess 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  * Permission is hereby granted, free of charge, to any person obtaining a copy
  10  * of this software and associated documentation files (the "Software"), to deal
  11  * in the Software without restriction, including without limitation the rights
  12  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  13  * copies of the Software, and to permit persons to whom the Software is
  14  * furnished to do so, subject to the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be included in
  17  * all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  22  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  23  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  24  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  25  * THE SOFTWARE.
  26  */
  27 #include <stdarg.h>
  28 #include <stdlib.h>
  29 #include <stdio.h>
  30 #include <string.h>
  31 #include <ctype.h>
  32 #include <unistd.h>
  33 #include <fcntl.h>
  34
  35 #include "lib.h"
  36 #include "allocate.h"
  37 #include "token.h"
  38 #include "parse.h"
  39 #include "symbol.h"
  40 #include "expression.h"
  41 #include "linearize.h"
  42
  43 static int context_increase(struct basic_block *bb, int entry)
  44 {
  45         int sum = 0;
  46         struct instruction *insn;
  47
  48         FOR_EACH_PTR(bb->insns, insn) {
  49                 int val;
  50                 if (!insn->bb)
  51                         continue;
  52                 if (insn->opcode != OP_CONTEXT)
  53                         continue;
  54                 val = insn->increment;
  55                 if (insn->check) {
  56                         int current = sum + entry;
  57                         if (!val) {
  58                                 if (!current)
  59                                         continue;
  60                         } else if (current >= val)
  61                                 continue;
  62                         warning(insn->pos, "context check failure");
  63                         continue;
  64                 }
  65                 sum += val;
  66         } END_FOR_EACH_PTR(insn);
  67         return sum;
  68 }
  69
  70 static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
  71 {
  72         if (Wcontext) {
  73                 struct symbol *sym = ep->name;
  74                 warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
  75         }
  76         return -1;
  77 }
  78
  79 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
  80
  81 static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
  82 {
  83         struct instruction *insn;
  84         struct basic_block *child;
  85
  86         insn = last_instruction(bb->insns);
  87         if (!insn)
  88                 return 0;
  89         if (insn->opcode == OP_RET)
  90                 return entry != exit ? imbalance(ep, bb, entry, exit, "wrong count at exit") : 0;
  91
  92         FOR_EACH_PTR(bb->children, child) {
  93                 if (check_bb_context(ep, child, entry, exit))
  94                         return -1;
  95         } END_FOR_EACH_PTR(child);
  96         return 0;
  97 }
  98
  99 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
 100 {
 101         if (!bb)
 102                 return 0;
 103         if (bb->context == entry)
 104                 return 0;
 105
 106         /* Now that's not good.. */
 107         if (bb->context >= 0)
 108                 return imbalance(ep, bb, entry, bb->context, "different lock contexts for basic block");
 109
 110         bb->context = entry;
 111         entry += context_increase(bb, entry);
 112         if (entry < 0)
 113                 return imbalance(ep, bb, entry, exit, "unexpected unlock");
 114
 115         return check_children(ep, bb, entry, exit);
 116 }
 117
 118 static void check_cast_instruction(struct instruction *insn)
 119 {
 120         struct symbol *orig_type = insn->orig_type;
 121         if (orig_type) {
 122                 int old = orig_type->bit_size;
 123                 int new = insn->size;
 124                 int oldsigned = (orig_type->ctype.modifiers & MOD_SIGNED) != 0;
 125                 int newsigned = insn->opcode == OP_SEXT;
 126
 127                 if (new > old) {
 128                         if (oldsigned == newsigned)
 129                                 return;
 130                         if (newsigned)
 131                                 return;
 132                         warning(insn->pos, "cast loses sign");
 133                         return;
 134                 }
 135                 if (new < old) {
 136                         warning(insn->pos, "cast drops bits");
 137                         return;
 138                 }
 139                 if (oldsigned == newsigned) {
 140                         warning(insn->pos, "cast wasn't removed");
 141                         return;
 142                 }
 143                 warning(insn->pos, "cast changes sign");
 144         }
 145 }
 146
 147 static void check_range_instruction(struct instruction *insn)
 148 {
 149         warning(insn->pos, "value out of range");
 150 }
 151
 152 static void check_byte_count(struct instruction *insn, pseudo_t count)
 153 {
 154         if (!count)
 155                 return;
 156         if (count->type == PSEUDO_VAL) {
 157                 unsigned long long val = count->value;
 158                 if (Wmemcpy_max_count && val > fmemcpy_max_count)
 159                         warning(insn->pos, "%s with byte count of %llu",
 160                                 show_ident(insn->func->sym->ident), val);
 161                 return;
 162         }
 163         /* OK, we could try to do the range analysis here */
 164 }
 165
 166 static pseudo_t argument(struct instruction *call, unsigned int argno)
 167 {
 168         pseudo_t args[8];
 169         struct ptr_list *arg_list = (struct ptr_list *) call->arguments;
 170
 171         argno--;
 172         if (linearize_ptr_list(arg_list, (void *)args, 8) > argno)
 173                 return args[argno];
 174         return NULL;
 175 }
 176
 177 static void check_memset(struct instruction *insn)
 178 {
 179         check_byte_count(insn, argument(insn, 3));
 180 }
 181
 182 #define check_memcpy check_memset
 183 #define check_ctu check_memset
 184 #define check_cfu check_memset
 185
 186 struct checkfn {
 187         struct ident *id;
 188         void (*check)(struct instruction *insn);
 189 };
 190
 191 static void check_call_instruction(struct instruction *insn)
 192 {
 193         pseudo_t fn = insn->func;
 194         struct ident *ident;
 195         static const struct checkfn check_fn[] = {
 196                 { &memset_ident, check_memset },
 197                 { &memcpy_ident, check_memcpy },
 198                 { &copy_to_user_ident, check_ctu },
 199                 { &copy_from_user_ident, check_cfu },
 200         };
 201         int i;
 202
 203         if (fn->type != PSEUDO_SYM)
 204                 return;
 205         ident = fn->sym->ident;
 206         if (!ident)
 207                 return;
 208         for (i = 0; i < ARRAY_SIZE(check_fn); i++) {
 209                 if (check_fn[i].id != ident)
 210                         continue;
 211                 check_fn[i].check(insn);
 212                 break;
 213         }
 214 }
 215
 216 static void check_one_instruction(struct instruction *insn)
 217 {
 218         switch (insn->opcode) {
 219         case OP_SEXT: case OP_ZEXT:
 220         case OP_TRUNC:
 221                 if (verbose)
 222                         check_cast_instruction(insn);
 223                 break;
 224         case OP_RANGE:
 225                 check_range_instruction(insn);
 226                 break;
 227         case OP_CALL:
 228                 check_call_instruction(insn);
 229                 break;
 230         default:
 231                 break;
 232         }
 233 }
 234
 235 static void check_bb_instructions(struct basic_block *bb)
 236 {
 237         struct instruction *insn;
 238         FOR_EACH_PTR(bb->insns, insn) {
 239                 if (!insn->bb)
 240                         continue;
 241                 check_one_instruction(insn);
 242         } END_FOR_EACH_PTR(insn);
 243 }
 244
 245 static void check_instructions(struct entrypoint *ep)
 246 {
 247         struct basic_block *bb;
 248         FOR_EACH_PTR(ep->bbs, bb) {
 249                 bb->context = -1;
 250                 check_bb_instructions(bb);
 251         } END_FOR_EACH_PTR(bb);
 252 }
 253
 254 static void check_context(struct entrypoint *ep)
 255 {
 256         struct symbol *sym = ep->name;
 257         struct context *context;
 258         unsigned int in_context = 0, out_context = 0;
 259
 260         if (Wuninitialized && verbose && ep->entry->bb->needs) {
 261                 pseudo_t pseudo;
 262                 FOR_EACH_PTR(ep->entry->bb->needs, pseudo) {
 263                         if (pseudo->type != PSEUDO_ARG)
 264                                 warning(sym->pos, "%s: possible uninitialized variable (%s)",
 265                                         show_ident(sym->ident), show_pseudo(pseudo));
 266                 } END_FOR_EACH_PTR(pseudo);
 267         }
 268
 269         check_instructions(ep);
 270
 271         FOR_EACH_PTR(sym->ctype.contexts, context) {
 272                 in_context += context->in;
 273                 out_context += context->out;
 274         } END_FOR_EACH_PTR(context);
 275         check_bb_context(ep, ep->entry->bb, in_context, out_context);
 276 }
 277
 278 /* list_compound_symbol - symbol info for arrays, structures, unions */
 279 static void list_compound_symbol(struct symbol *sym)
 280 {
 281         struct symbol *base;
 282
 283         /* Only show symbols that have a positive size */
 284         if (sym->bit_size <= 0)
 285                 return;
 286         if (!sym->ctype.base_type)
 287                 return;
 288         /* Don't show unnamed types */
 289         if (!sym->ident)
 290                 return;
 291
 292         if (sym->type == SYM_NODE)
 293                 base = sym->ctype.base_type;
 294         else
 295                 base = sym;
 296         switch (base->type) {
 297         case SYM_STRUCT: case SYM_UNION: case SYM_ARRAY:
 298                 break;
 299         default:
 300                 return;
 301         }
 302
 303         info(sym->pos, "%s: compound size %u, alignment %lu",
 304                 show_typename(sym),
 305                 bits_to_bytes(sym->bit_size),
 306                 sym->ctype.alignment);
 307 }
 308
 309 static void check_symbols(struct symbol_list *list)
 310 {
 311         struct symbol *sym;
 312
 313         FOR_EACH_PTR(list, sym) {
 314                 struct entrypoint *ep;
 315
 316                 expand_symbol(sym);
 317                 ep = linearize_symbol(sym);
 318                 if (ep && ep->entry) {
 319                         if (dbg_entry)
 320                                 show_entry(ep);
 321
 322                         check_context(ep);
 323                 }
 324                 if (dbg_compound)
 325                         list_compound_symbol(sym);
 326         } END_FOR_EACH_PTR(sym);
 327
 328         if (Wsparse_error && die_if_error)
 329                 exit(1);
 330 }
 331
 332 int main(int argc, char **argv)
 333 {
 334         struct string_list *filelist = NULL;
 335         char *file;
 336
 337         // by default ignore -o <file>
 338         do_output = 0;
 339
 340         // Expand, linearize and show it.
 341         check_symbols(sparse_initialize(argc, argv, &filelist));
 342         FOR_EACH_PTR(filelist, file) {
 343                 check_symbols(sparse(file));
 344         } END_FOR_EACH_PTR(file);
 345
 346         report_stats();
 347         return 0;
 348 }