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