Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 287 lines (251 sloc) 6.562 kb
b23fc8af » Linus Torvalds
2003-04-07 Add "check" program that just evaluates the tree and does nothing
1 /*
2 * Example trivial client program that uses the sparse library
cef10da3 » Josh Triplett
2007-03-09 Fix typos in comments
3 * to tokenize, preprocess and parse a C file, and prints out
b23fc8af » Linus Torvalds
2003-04-07 Add "check" program that just evaluates the tree and does nothing
4 * the results.
5 *
51df7631 » Linus Torvalds
2003-04-15 Start updating the copyright license comments to the OSL,
6 * Copyright (C) 2003 Transmeta Corp.
3234fa5b » Linus Torvalds
2004-11-17 Update copyright notices a bit.
7 * 2003-2004 Linus Torvalds
51df7631 » Linus Torvalds
2003-04-15 Start updating the copyright license comments to the OSL,
8 *
9 * Licensed under the Open Software License version 1.1
b23fc8af » Linus Torvalds
2003-04-07 Add "check" program that just evaluates the tree and does nothing
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"
2035e136 » Linus Torvalds
2004-12-02 Split out the blob allocator from lib.c into allocate.c.
20 #include "allocate.h"
b23fc8af » Linus Torvalds
2003-04-07 Add "check" program that just evaluates the tree and does nothing
21 #include "token.h"
22 #include "parse.h"
23 #include "symbol.h"
24 #include "expression.h"
64afe052 » Linus Torvalds
2004-07-24 Ok, enable linearization in "check" (aka sparse)
25 #include "linearize.h"
b23fc8af » Linus Torvalds
2003-04-07 Add "check" program that just evaluates the tree and does nothing
26
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
27 static int context_increase(struct basic_block *bb, int entry)
6dcc36ae » jmberg
2008-04-23 fix bug in context tracking code
28 {
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
29 int sum = 0;
30 struct instruction *insn;
6dcc36ae » jmberg
2008-04-23 fix bug in context tracking code
31
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
32 FOR_EACH_PTR(bb->insns, insn) {
33 int val;
34 if (insn->opcode != OP_CONTEXT)
6dcc36ae » jmberg
2008-04-23 fix bug in context tracking code
35 continue;
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
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)
c5b808c9 » jmberg
2008-04-10 make sparse keep its promise about context tracking
43 continue;
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
44 warning(insn->pos, "context check failure");
6663e107 » jmberg
2008-04-11 improve -Wcontext code and messages
45 continue;
46 }
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
47 sum += val;
48 } END_FOR_EACH_PTR(insn);
49 return sum;
6663e107 » jmberg
2008-04-11 improve -Wcontext code and messages
50 }
51
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
52 static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
6663e107 » jmberg
2008-04-11 improve -Wcontext code and messages
53 {
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
54 if (Wcontext) {
55 struct symbol *sym = ep->name;
56 warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
6663e107 » jmberg
2008-04-11 improve -Wcontext code and messages
57 }
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
58 return -1;
6663e107 » jmberg
2008-04-11 improve -Wcontext code and messages
59 }
60
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
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)
92324d8f » Linus Torvalds
2004-10-22 Make "check" (aka "sparse") check for context imbalance.
64 {
65 struct instruction *insn;
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
66 struct basic_block *child;
92324d8f » Linus Torvalds
2004-10-22 Make "check" (aka "sparse") check for context imbalance.
67
68 insn = last_instruction(bb->insns);
738fe3b7 » Linus Torvalds
2004-10-22 Duh. It's ok to not have any instructions in a bb.
69 if (!insn)
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
70 return 0;
71 if (insn->opcode == OP_RET)
72 return entry != exit ? imbalance(ep, bb, entry, exit, "wrong count at exit") : 0;
92324d8f » Linus Torvalds
2004-10-22 Make "check" (aka "sparse") check for context imbalance.
73
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
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;
6dcc36ae » jmberg
2008-04-23 fix bug in context tracking code
79 }
92324d8f » Linus Torvalds
2004-10-22 Make "check" (aka "sparse") check for context imbalance.
80
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
81 static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
6dcc36ae » jmberg
2008-04-23 fix bug in context tracking code
82 {
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
83 if (!bb)
84 return 0;
85 if (bb->context == entry)
86 return 0;
6dcc36ae » jmberg
2008-04-23 fix bug in context tracking code
87
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
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");
6dcc36ae » jmberg
2008-04-23 fix bug in context tracking code
91
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
92 bb->context = entry;
93 entry += context_increase(bb, entry);
94 if (entry < 0)
95 return imbalance(ep, bb, entry, exit, "unexpected unlock");
6dcc36ae » jmberg
2008-04-23 fix bug in context tracking code
96
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
97 return check_children(ep, bb, entry, exit);
92324d8f » Linus Torvalds
2004-10-22 Make "check" (aka "sparse") check for context imbalance.
98 }
99
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
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;
50716970 » Linus Torvalds
2005-02-04 Use the new per-instruction position information for better
114 warning(insn->pos, "cast loses sign");
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
115 return;
116 }
117 if (new < old) {
50716970 » Linus Torvalds
2005-02-04 Use the new per-instruction position information for better
118 warning(insn->pos, "cast drops bits");
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
119 return;
120 }
121 if (oldsigned == newsigned) {
50716970 » Linus Torvalds
2005-02-04 Use the new per-instruction position information for better
122 warning(insn->pos, "cast wasn't removed");
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
123 return;
124 }
50716970 » Linus Torvalds
2005-02-04 Use the new per-instruction position information for better
125 warning(insn->pos, "cast changes sign");
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
126 }
127 }
128
4b369282 » Linus Torvalds
2005-02-04 Add compile-time "range-check" infrastructure to sparse
129 static void check_range_instruction(struct instruction *insn)
130 {
50716970 » Linus Torvalds
2005-02-04 Use the new per-instruction position information for better
131 warning(insn->pos, "value out of range");
4b369282 » Linus Torvalds
2005-02-04 Add compile-time "range-check" infrastructure to sparse
132 }
133
1b021084 » Linus Torvalds
2005-02-11 Make "check" (aka sparse) check arguments to some functions.
134 static void check_byte_count(struct instruction *insn, pseudo_t count)
135 {
260a278a » looxix
2005-06-27 [PATCH] avoid segfault in check_byte_count()
136 if (!count)
137 return;
1b021084 » Linus Torvalds
2005-02-11 Make "check" (aka sparse) check arguments to some functions.
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 }
cef10da3 » Josh Triplett
2007-03-09 Fix typos in comments
145 /* OK, we could try to do the range analysis here */
1b021084 » Linus Torvalds
2005-02-11 Make "check" (aka sparse) check arguments to some functions.
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;
7988e483 » jpokorny
2011-04-26 use ARRAY_SIZE() when possible (continued)
190 for (i = 0; i < ARRAY_SIZE(check_fn); i++) {
1b021084 » Linus Torvalds
2005-02-11 Make "check" (aka sparse) check arguments to some functions.
191 if (check_fn[i].id != ident)
192 continue;
193 check_fn[i].check(insn);
194 break;
195 }
196 }
197
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
198 static void check_one_instruction(struct instruction *insn)
199 {
200 switch (insn->opcode) {
201 case OP_CAST: case OP_SCAST:
4b369282 » Linus Torvalds
2005-02-04 Add compile-time "range-check" infrastructure to sparse
202 if (verbose)
203 check_cast_instruction(insn);
204 break;
205 case OP_RANGE:
206 check_range_instruction(insn);
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
207 break;
1b021084 » Linus Torvalds
2005-02-11 Make "check" (aka sparse) check arguments to some functions.
208 case OP_CALL:
209 check_call_instruction(insn);
210 break;
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
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
92324d8f » Linus Torvalds
2004-10-22 Make "check" (aka "sparse") check for context imbalance.
234 static void check_context(struct entrypoint *ep)
235 {
cf299d81 » Linus Torvalds
2004-10-23 Use the in_context/out_context information in the context balance
236 struct symbol *sym = ep->name;
37475a6c » Josh Triplett
2006-08-30 [PATCH] Parse and track multiple contexts by expression
237 struct context *context;
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
238 unsigned int in_context = 0, out_context = 0;
cf299d81 » Linus Torvalds
2004-10-23 Use the in_context/out_context information in the context balance
239
6ab5eb55 » Josh Triplett
2006-08-29 Add -Wno-uninitialized
240 if (Wuninitialized && verbose && ep->entry->bb->needs) {
d88ba072 » Linus Torvalds
2004-12-04 Now that we track argument pseudo liveness, make
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 }
55a0bc25 » Linus Torvalds
2004-11-29 Allow multiple levels of verbosity, and print out the _really_
248
4b369282 » Linus Torvalds
2005-02-04 Add compile-time "range-check" infrastructure to sparse
249 check_instructions(ep);
6ca9d753 » Linus Torvalds
2005-02-04 Make "check" (aka "sparse") check data-dropping casts.
250
37475a6c » Josh Triplett
2006-08-30 [PATCH] Parse and track multiple contexts by expression
251 FOR_EACH_PTR(sym->ctype.contexts, context) {
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
252 in_context += context->in;
253 out_context += context->out;
37475a6c » Josh Triplett
2006-08-30 [PATCH] Parse and track multiple contexts by expression
254 } END_FOR_EACH_PTR(context);
2479d0f7 » jmberg
2008-12-23 Revert the context tracking code
255 check_bb_context(ep, ep->entry->bb, in_context, out_context);
92324d8f » Linus Torvalds
2004-10-22 Make "check" (aka "sparse") check for context imbalance.
256 }
257
1342c130 » Linus Torvalds
2004-11-23 Make the new "sparse()" interface even more painfully obvious.
258 static void check_symbols(struct symbol_list *list)
b23fc8af » Linus Torvalds
2003-04-07 Add "check" program that just evaluates the tree and does nothing
259 {
f9344b85 » Linus Torvalds
2004-10-22 Get rid of the old "iterate()" interfaces.
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);
9a355441 » sparsecli
2007-02-23 Adding debug option for showing the linearized instruction.
267 if (ep) {
268 if (dbg_entry)
269 show_entry(ep);
270
f9344b85 » Linus Torvalds
2004-10-22 Get rid of the old "iterate()" interfaces.
271 check_context(ep);
9a355441 » sparsecli
2007-02-23 Adding debug option for showing the linearized instruction.
272 }
f9344b85 » Linus Torvalds
2004-10-22 Get rid of the old "iterate()" interfaces.
273 } END_FOR_EACH_PTR(sym);
b23fc8af » Linus Torvalds
2003-04-07 Add "check" program that just evaluates the tree and does nothing
274 }
275
276 int main(int argc, char **argv)
277 {
4ad8ad70 » sparsecli
2006-11-30 cleanup write to argument array hack
278 struct string_list *filelist = NULL;
279 char *file;
280
3451bba6 » Linus Torvalds
2004-11-10 Make "translation_unit()" do symbol evaluation too.
281 // Expand, linearize and show it.
4ad8ad70 » sparsecli
2006-11-30 cleanup write to argument array hack
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);
b23fc8af » Linus Torvalds
2003-04-07 Add "check" program that just evaluates the tree and does nothing
286 return 0;
287 }
Something went wrong with that request. Please try again.