implied: get rid of the ->implied member
[smatch.git] / sparse.c
blob62a71c332b364a45b99c69a174507a6fe3232784
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.
6 * Copyright (C) 2003 Transmeta Corp.
7 * 2003-2004 Linus Torvalds
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:
16 * The above copyright notice and this permission notice shall be included in
17 * all copies or substantial portions of the Software.
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.
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>
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"
43 static int context_increase(struct basic_block *bb, int entry)
45 int sum = 0;
46 struct instruction *insn;
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;
63 sum += val;
64 } END_FOR_EACH_PTR(insn);
65 return sum;
68 static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
70 if (Wcontext) {
71 struct symbol *sym = ep->name;
72 warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
74 return -1;
77 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
79 static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
81 struct instruction *insn;
82 struct basic_block *child;
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;
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;
97 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
99 if (!bb)
100 return 0;
101 if (bb->context == entry)
102 return 0;
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");
108 bb->context = entry;
109 entry += context_increase(bb, entry);
110 if (entry < 0)
111 return imbalance(ep, bb, entry, exit, "unexpected unlock");
113 return check_children(ep, bb, entry, exit);
116 static void check_cast_instruction(struct instruction *insn)
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;
125 if (new > old) {
126 if (oldsigned == newsigned)
127 return;
128 if (newsigned)
129 return;
130 warning(insn->pos, "cast loses sign");
131 return;
133 if (new < old) {
134 warning(insn->pos, "cast drops bits");
135 return;
137 if (oldsigned == newsigned) {
138 warning(insn->pos, "cast wasn't removed");
139 return;
141 warning(insn->pos, "cast changes sign");
145 static void check_range_instruction(struct instruction *insn)
147 warning(insn->pos, "value out of range");
150 static void check_byte_count(struct instruction *insn, pseudo_t count)
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;
161 /* OK, we could try to do the range analysis here */
164 static pseudo_t argument(struct instruction *call, unsigned int argno)
166 pseudo_t args[8];
167 struct ptr_list *arg_list = (struct ptr_list *) call->arguments;
169 argno--;
170 if (linearize_ptr_list(arg_list, (void *)args, 8) > argno)
171 return args[argno];
172 return NULL;
175 static void check_memset(struct instruction *insn)
177 check_byte_count(insn, argument(insn, 3));
180 #define check_memcpy check_memset
181 #define check_ctu check_memset
182 #define check_cfu check_memset
184 struct checkfn {
185 struct ident *id;
186 void (*check)(struct instruction *insn);
189 static void check_call_instruction(struct instruction *insn)
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 },
199 int i;
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;
214 static void check_one_instruction(struct instruction *insn)
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;
232 static void check_bb_instructions(struct basic_block *bb)
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);
242 static void check_instructions(struct entrypoint *ep)
244 struct basic_block *bb;
245 FOR_EACH_PTR(ep->bbs, bb) {
246 check_bb_instructions(bb);
247 } END_FOR_EACH_PTR(bb);
250 static void check_context(struct entrypoint *ep)
252 struct symbol *sym = ep->name;
253 struct context *context;
254 unsigned int in_context = 0, out_context = 0;
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);
265 check_instructions(ep);
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);
274 static void check_symbols(struct symbol_list *list)
276 struct symbol *sym;
278 FOR_EACH_PTR(list, sym) {
279 struct entrypoint *ep;
281 expand_symbol(sym);
282 ep = linearize_symbol(sym);
283 if (ep) {
284 if (dbg_entry)
285 show_entry(ep);
287 check_context(ep);
289 } END_FOR_EACH_PTR(sym);
291 if (die_if_error)
292 exit(1);
295 int main(int argc, char **argv)
297 struct string_list *filelist = NULL;
298 char *file;
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;