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
43static 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
70static 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
79static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
80
81static 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
99static 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
118static 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
147static void check_range_instruction(struct instruction *insn)
148{
149	warning(insn->pos, "value out of range");
150}
151
152static 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
166static void check_memset(struct instruction *insn)
167{
168	check_byte_count(insn, ptr_list_nth(insn->arguments, 3));
169}
170
171#define check_memcpy check_memset
172#define check_ctu check_memset
173#define check_cfu check_memset
174
175struct checkfn {
176	struct ident *id;
177	void (*check)(struct instruction *insn);
178};
179
180static void check_call_instruction(struct instruction *insn)
181{
182	pseudo_t fn = insn->func;
183	struct ident *ident;
184	static const struct checkfn check_fn[] = {
185		{ &memset_ident, check_memset },
186		{ &memcpy_ident, check_memcpy },
187		{ &copy_to_user_ident, check_ctu },
188		{ &copy_from_user_ident, check_cfu },
189	};
190	int i;
191
192	if (fn->type != PSEUDO_SYM)
193		return;
194	ident = fn->sym->ident;
195	if (!ident)
196		return;
197	for (i = 0; i < ARRAY_SIZE(check_fn); i++) {
198		if (check_fn[i].id != ident)
199			continue;
200		check_fn[i].check(insn);
201		break;
202	}
203}
204
205static void check_one_instruction(struct instruction *insn)
206{
207	switch (insn->opcode) {
208	case OP_SEXT: case OP_ZEXT:
209	case OP_TRUNC:
210		if (verbose)
211			check_cast_instruction(insn);
212		break;
213	case OP_RANGE:
214		check_range_instruction(insn);
215		break;
216	case OP_CALL:
217		check_call_instruction(insn);
218		break;
219	default:
220		break;
221	}
222}
223
224static void check_bb_instructions(struct basic_block *bb)
225{
226	struct instruction *insn;
227	FOR_EACH_PTR(bb->insns, insn) {
228		if (!insn->bb)
229			continue;
230		check_one_instruction(insn);
231	} END_FOR_EACH_PTR(insn);
232}
233
234static void check_instructions(struct entrypoint *ep)
235{
236	struct basic_block *bb;
237	FOR_EACH_PTR(ep->bbs, bb) {
238		bb->context = -1;
239		check_bb_instructions(bb);
240	} END_FOR_EACH_PTR(bb);
241}
242
243static void check_context(struct entrypoint *ep)
244{
245	struct symbol *sym = ep->name;
246	struct context *context;
247	unsigned int in_context = 0, out_context = 0;
248
249	if (Wuninitialized && verbose && ep->entry->bb->needs) {
250		pseudo_t pseudo;
251		FOR_EACH_PTR(ep->entry->bb->needs, pseudo) {
252			if (pseudo->type != PSEUDO_ARG)
253				warning(sym->pos, "%s: possible uninitialized variable (%s)",
254					show_ident(sym->ident), show_pseudo(pseudo));
255		} END_FOR_EACH_PTR(pseudo);
256	}
257
258	check_instructions(ep);
259
260	FOR_EACH_PTR(sym->ctype.contexts, context) {
261		in_context += context->in;
262		out_context += context->out;
263	} END_FOR_EACH_PTR(context);
264	check_bb_context(ep, ep->entry->bb, in_context, out_context);
265}
266
267/* list_compound_symbol - symbol info for arrays, structures, unions */
268static void list_compound_symbol(struct symbol *sym)
269{
270	struct symbol *base;
271
272	/* Only show symbols that have a positive size */
273	if (sym->bit_size <= 0)
274		return;
275	if (!sym->ctype.base_type)
276		return;
277	/* Don't show unnamed types */
278	if (!sym->ident)
279		return;
280
281	if (sym->type == SYM_NODE)
282		base = sym->ctype.base_type;
283	else
284		base = sym;
285	switch (base->type) {
286	case SYM_STRUCT: case SYM_UNION: case SYM_ARRAY:
287		break;
288	default:
289		return;
290	}
291
292	info(sym->pos, "%s: compound size %u, alignment %lu",
293		show_typename(sym),
294		bits_to_bytes(sym->bit_size),
295		sym->ctype.alignment);
296}
297
298static void check_symbols(struct symbol_list *list)
299{
300	struct symbol *sym;
301
302	FOR_EACH_PTR(list, sym) {
303		struct entrypoint *ep;
304
305		expand_symbol(sym);
306		ep = linearize_symbol(sym);
307		if (ep && ep->entry) {
308			if (dbg_entry)
309				show_entry(ep);
310
311			check_context(ep);
312		}
313		if (dbg_compound)
314			list_compound_symbol(sym);
315	} END_FOR_EACH_PTR(sym);
316
317	if (Wsparse_error && die_if_error)
318		exit(1);
319}
320
321int main(int argc, char **argv)
322{
323	struct string_list *filelist = NULL;
324	char *file;
325
326	// by default ignore -o <file>
327	do_output = 0;
328
329	// Expand, linearize and show it.
330	check_symbols(sparse_initialize(argc, argv, &filelist));
331	FOR_EACH_PTR(filelist, file) {
332		check_symbols(sparse(file));
333	} END_FOR_EACH_PTR(file);
334
335	report_stats();
336	return 0;
337}
338