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->opcode != OP_CONTEXT)
  51                         continue;
  52                 val = insn->increment;
  53                 if (insn->check) {
  54                         int current = sum + entry;
  55                         if (!val) {
  56                                 if (!current)
  57                                         continue;
  58                         } else if (current >= val)
  59                                 continue;
  60                         warning(insn->pos, "context check failure");
  61                         continue;
  62                 }
  63                 sum += val;
  64         } END_FOR_EACH_PTR(insn);
  65         return sum;
  66 }
  67
  68 static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
  69 {
  70         if (Wcontext) {
  71                 struct symbol *sym = ep->name;
  72                 warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
  73         }
  74         return -1;
  75 }
  76
  77 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
  78
  79 static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
  80 {
  81         struct instruction *insn;
  82         struct basic_block *child;
  83
  84         insn = last_instruction(bb->insns);
  85         if (!insn)
  86                 return 0;
  87         if (insn->opcode == OP_RET)
  88                 return entry != exit ? imbalance(ep, bb, entry, exit, "wrong count at exit") : 0;
  89
  90         FOR_EACH_PTR(bb->children, child) {
  91                 if (check_bb_context(ep, child, entry, exit))
  92                         return -1;
  93         } END_FOR_EACH_PTR(child);
  94         return 0;
  95 }
  96
  97 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
  98 {
  99         if (!bb)
 100                 return 0;
 101         if (bb->context == entry)
 102                 return 0;
 103
 104         /* Now that's not good.. */
 105         if (bb->context >= 0)
 106                 return imbalance(ep, bb, entry, bb->context, "different lock contexts for basic block");
 107
 108         bb->context = entry;
 109         entry += context_increase(bb, entry);
 110         if (entry < 0)
 111                 return imbalance(ep, bb, entry, exit, "unexpected unlock");
 112
 113         return check_children(ep, bb, entry, exit);
 114 }
 115
 116 static void check_cast_instruction(struct instruction *insn)
 117 {
 118         struct symbol *orig_type = insn->orig_type;
 119         if (orig_type) {
 120                 int old = orig_type->bit_size;
 121                 int new = insn->size;
 122                 int oldsigned = (orig_type->ctype.modifiers & MOD_SIGNED) != 0;
 123                 int newsigned = insn->opcode == OP_SCAST;
 124
 125                 if (new > old) {
 126                         if (oldsigned == newsigned)
 127                                 return;
 128                         if (newsigned)
 129                                 return;
 130                         warning(insn->pos, "cast loses sign");
 131                         return;
 132                 }
 133                 if (new < old) {
 134                         warning(insn->pos, "cast drops bits");
 135                         return;
 136                 }
 137                 if (oldsigned == newsigned) {
 138                         warning(insn->pos, "cast wasn't removed");
 139                         return;
 140                 }
 141                 warning(insn->pos, "cast changes sign");
 142         }
 143 }
 144
 145 static void check_range_instruction(struct instruction *insn)
 146 {
 147         warning(insn->pos, "value out of range");
 148 }
 149
 150 static void check_byte_count(struct instruction *insn, pseudo_t count)
 151 {
 152         if (!count)
 153                 return;
 154         if (count->type == PSEUDO_VAL) {
 155                 long long val = count->value;
 156                 if (val <= 0 || val > 100000)
 157                         warning(insn->pos, "%s with byte count of %lld",
 158                                 show_ident(insn->func->sym->ident), val);
 159                 return;
 160         }
 161         /* OK, we could try to do the range analysis here */
 162 }
 163
 164 static pseudo_t argument(struct instruction *call, unsigned int argno)
 165 {
 166         pseudo_t args[8];
 167         struct ptr_list *arg_list = (struct ptr_list *) call->arguments;
 168
 169         argno--;
 170         if (linearize_ptr_list(arg_list, (void *)args, 8) > argno)
 171                 return args[argno];
 172         return NULL;
 173 }
 174
 175 static void check_memset(struct instruction *insn)
 176 {
 177         check_byte_count(insn, argument(insn, 3));
 178 }
 179
 180 #define check_memcpy check_memset
 181 #define check_ctu check_memset
 182 #define check_cfu check_memset
 183
 184 struct checkfn {
 185         struct ident *id;
 186         void (*check)(struct instruction *insn);
 187 };
 188
 189 static void check_call_instruction(struct instruction *insn)
 190 {
 191         pseudo_t fn = insn->func;
 192         struct ident *ident;
 193         static const struct checkfn check_fn[] = {
 194                 { &memset_ident, check_memset },
 195                 { &memcpy_ident, check_memcpy },
 196                 { &copy_to_user_ident, check_ctu },
 197                 { &copy_from_user_ident, check_cfu },
 198         };
 199         int i;
 200
 201         if (fn->type != PSEUDO_SYM)
 202                 return;
 203         ident = fn->sym->ident;
 204         if (!ident)
 205                 return;
 206         for (i = 0; i < ARRAY_SIZE(check_fn); i++) {
 207                 if (check_fn[i].id != ident)
 208                         continue;
 209                 check_fn[i].check(insn);
 210                 break;
 211         }
 212 }
 213
 214 static void check_one_instruction(struct instruction *insn)
 215 {
 216         switch (insn->opcode) {
 217         case OP_CAST: case OP_SCAST:
 218                 if (verbose)
 219                         check_cast_instruction(insn);
 220                 break;
 221         case OP_RANGE:
 222                 check_range_instruction(insn);
 223                 break;
 224         case OP_CALL:
 225                 check_call_instruction(insn);
 226                 break;
 227         default:
 228                 break;
 229         }
 230 }
 231
 232 static void check_bb_instructions(struct basic_block *bb)
 233 {
 234         struct instruction *insn;
 235         FOR_EACH_PTR(bb->insns, insn) {
 236                 if (!insn->bb)
 237                         continue;
 238                 check_one_instruction(insn);
 239         } END_FOR_EACH_PTR(insn);
 240 }
 241
 242 static void check_instructions(struct entrypoint *ep)
 243 {
 244         struct basic_block *bb;
 245         FOR_EACH_PTR(ep->bbs, bb) {
 246                 check_bb_instructions(bb);
 247         } END_FOR_EACH_PTR(bb);
 248 }
 249
 250 static void check_context(struct entrypoint *ep)
 251 {
 252         struct symbol *sym = ep->name;
 253         struct context *context;
 254         unsigned int in_context = 0, out_context = 0;
 255
 256         if (Wuninitialized && verbose && ep->entry->bb->needs) {
 257                 pseudo_t pseudo;
 258                 FOR_EACH_PTR(ep->entry->bb->needs, pseudo) {
 259                         if (pseudo->type != PSEUDO_ARG)
 260                                 warning(sym->pos, "%s: possible uninitialized variable (%s)",
 261                                         show_ident(sym->ident), show_pseudo(pseudo));
 262                 } END_FOR_EACH_PTR(pseudo);
 263         }
 264
 265         check_instructions(ep);
 266
 267         FOR_EACH_PTR(sym->ctype.attribute->contexts, context) {
 268                 in_context += context->in;
 269                 out_context += context->out;
 270         } END_FOR_EACH_PTR(context);
 271         check_bb_context(ep, ep->entry->bb, in_context, out_context);
 272 }
 273
 274 static void check_symbols(struct symbol_list *list)
 275 {
 276         struct symbol *sym;
 277
 278         FOR_EACH_PTR(list, sym) {
 279                 struct entrypoint *ep;
 280
 281                 expand_symbol(sym);
 282                 ep = linearize_symbol(sym);
 283                 if (ep) {
 284                         if (dbg_entry)
 285                                 show_entry(ep);
 286
 287                         check_context(ep);
 288                 }
 289         } END_FOR_EACH_PTR(sym);
 290
 291         if (die_if_error)
 292                 exit(1);
 293 }
 294
 295 int main(int argc, char **argv)
 296 {
 297         struct string_list *filelist = NULL;
 298         char *file;
 299
 300         // Expand, linearize and show it.
 301         check_symbols(sparse_initialize(argc, argv, &filelist));
 302         FOR_EACH_PTR_NOTAG(filelist, file) {
 303                 check_symbols(sparse(file));
 304         } END_FOR_EACH_PTR_NOTAG(file);
 305         return 0;
 306 }