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 { ©_to_user_ident, check_ctu },
199 { ©_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 }