11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * Example trivial client program that uses the sparse library
31f5207b7SJohn Levon * to tokenize, preprocess and parse a C file, and prints out
41f5207b7SJohn Levon * the results.
51f5207b7SJohn Levon *
61f5207b7SJohn Levon * Copyright (C) 2003 Transmeta Corp.
71f5207b7SJohn Levon * 2003-2004 Linus Torvalds
81f5207b7SJohn Levon *
91f5207b7SJohn Levon * Permission is hereby granted, free of charge, to any person obtaining a copy
101f5207b7SJohn Levon * of this software and associated documentation files (the "Software"), to deal
111f5207b7SJohn Levon * in the Software without restriction, including without limitation the rights
121f5207b7SJohn Levon * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
131f5207b7SJohn Levon * copies of the Software, and to permit persons to whom the Software is
141f5207b7SJohn Levon * furnished to do so, subject to the following conditions:
151f5207b7SJohn Levon *
161f5207b7SJohn Levon * The above copyright notice and this permission notice shall be included in
171f5207b7SJohn Levon * all copies or substantial portions of the Software.
181f5207b7SJohn Levon *
191f5207b7SJohn Levon * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
201f5207b7SJohn Levon * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
211f5207b7SJohn Levon * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
221f5207b7SJohn Levon * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
231f5207b7SJohn Levon * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
241f5207b7SJohn Levon * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
251f5207b7SJohn Levon * THE SOFTWARE.
261f5207b7SJohn Levon */
271f5207b7SJohn Levon #include <stdarg.h>
281f5207b7SJohn Levon #include <stdlib.h>
291f5207b7SJohn Levon #include <stdio.h>
301f5207b7SJohn Levon #include <string.h>
311f5207b7SJohn Levon #include <ctype.h>
321f5207b7SJohn Levon #include <unistd.h>
331f5207b7SJohn Levon #include <fcntl.h>
341f5207b7SJohn Levon
351f5207b7SJohn Levon #include "lib.h"
361f5207b7SJohn Levon #include "allocate.h"
371f5207b7SJohn Levon #include "token.h"
381f5207b7SJohn Levon #include "parse.h"
391f5207b7SJohn Levon #include "symbol.h"
401f5207b7SJohn Levon #include "expression.h"
411f5207b7SJohn Levon #include "linearize.h"
421f5207b7SJohn Levon
context_increase(struct basic_block * bb,int entry)431f5207b7SJohn Levon static int context_increase(struct basic_block *bb, int entry)
441f5207b7SJohn Levon {
451f5207b7SJohn Levon int sum = 0;
461f5207b7SJohn Levon struct instruction *insn;
471f5207b7SJohn Levon
481f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
491f5207b7SJohn Levon int val;
50*c85f09ccSJohn Levon if (!insn->bb)
51*c85f09ccSJohn Levon continue;
521f5207b7SJohn Levon if (insn->opcode != OP_CONTEXT)
531f5207b7SJohn Levon continue;
541f5207b7SJohn Levon val = insn->increment;
551f5207b7SJohn Levon if (insn->check) {
561f5207b7SJohn Levon int current = sum + entry;
571f5207b7SJohn Levon if (!val) {
581f5207b7SJohn Levon if (!current)
591f5207b7SJohn Levon continue;
601f5207b7SJohn Levon } else if (current >= val)
611f5207b7SJohn Levon continue;
621f5207b7SJohn Levon warning(insn->pos, "context check failure");
631f5207b7SJohn Levon continue;
641f5207b7SJohn Levon }
651f5207b7SJohn Levon sum += val;
661f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
671f5207b7SJohn Levon return sum;
681f5207b7SJohn Levon }
691f5207b7SJohn Levon
imbalance(struct entrypoint * ep,struct basic_block * bb,int entry,int exit,const char * why)701f5207b7SJohn Levon static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
711f5207b7SJohn Levon {
721f5207b7SJohn Levon if (Wcontext) {
731f5207b7SJohn Levon struct symbol *sym = ep->name;
741f5207b7SJohn Levon warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
751f5207b7SJohn Levon }
761f5207b7SJohn Levon return -1;
771f5207b7SJohn Levon }
781f5207b7SJohn Levon
791f5207b7SJohn Levon static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
801f5207b7SJohn Levon
check_children(struct entrypoint * ep,struct basic_block * bb,int entry,int exit)811f5207b7SJohn Levon static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
821f5207b7SJohn Levon {
831f5207b7SJohn Levon struct instruction *insn;
841f5207b7SJohn Levon struct basic_block *child;
851f5207b7SJohn Levon
861f5207b7SJohn Levon insn = last_instruction(bb->insns);
871f5207b7SJohn Levon if (!insn)
881f5207b7SJohn Levon return 0;
891f5207b7SJohn Levon if (insn->opcode == OP_RET)
901f5207b7SJohn Levon return entry != exit ? imbalance(ep, bb, entry, exit, "wrong count at exit") : 0;
911f5207b7SJohn Levon
921f5207b7SJohn Levon FOR_EACH_PTR(bb->children, child) {
931f5207b7SJohn Levon if (check_bb_context(ep, child, entry, exit))
941f5207b7SJohn Levon return -1;
951f5207b7SJohn Levon } END_FOR_EACH_PTR(child);
961f5207b7SJohn Levon return 0;
971f5207b7SJohn Levon }
981f5207b7SJohn Levon
check_bb_context(struct entrypoint * ep,struct basic_block * bb,int entry,int exit)991f5207b7SJohn Levon static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
1001f5207b7SJohn Levon {
1011f5207b7SJohn Levon if (!bb)
1021f5207b7SJohn Levon return 0;
1031f5207b7SJohn Levon if (bb->context == entry)
1041f5207b7SJohn Levon return 0;
1051f5207b7SJohn Levon
1061f5207b7SJohn Levon /* Now that's not good.. */
1071f5207b7SJohn Levon if (bb->context >= 0)
1081f5207b7SJohn Levon return imbalance(ep, bb, entry, bb->context, "different lock contexts for basic block");
1091f5207b7SJohn Levon
1101f5207b7SJohn Levon bb->context = entry;
1111f5207b7SJohn Levon entry += context_increase(bb, entry);
1121f5207b7SJohn Levon if (entry < 0)
1131f5207b7SJohn Levon return imbalance(ep, bb, entry, exit, "unexpected unlock");
1141f5207b7SJohn Levon
1151f5207b7SJohn Levon return check_children(ep, bb, entry, exit);
1161f5207b7SJohn Levon }
1171f5207b7SJohn Levon
check_cast_instruction(struct instruction * insn)1181f5207b7SJohn Levon static void check_cast_instruction(struct instruction *insn)
1191f5207b7SJohn Levon {
1201f5207b7SJohn Levon struct symbol *orig_type = insn->orig_type;
1211f5207b7SJohn Levon if (orig_type) {
1221f5207b7SJohn Levon int old = orig_type->bit_size;
1231f5207b7SJohn Levon int new = insn->size;
1241f5207b7SJohn Levon int oldsigned = (orig_type->ctype.modifiers & MOD_SIGNED) != 0;
125*c85f09ccSJohn Levon int newsigned = insn->opcode == OP_SEXT;
1261f5207b7SJohn Levon
1271f5207b7SJohn Levon if (new > old) {
1281f5207b7SJohn Levon if (oldsigned == newsigned)
1291f5207b7SJohn Levon return;
1301f5207b7SJohn Levon if (newsigned)
1311f5207b7SJohn Levon return;
1321f5207b7SJohn Levon warning(insn->pos, "cast loses sign");
1331f5207b7SJohn Levon return;
1341f5207b7SJohn Levon }
1351f5207b7SJohn Levon if (new < old) {
1361f5207b7SJohn Levon warning(insn->pos, "cast drops bits");
1371f5207b7SJohn Levon return;
1381f5207b7SJohn Levon }
1391f5207b7SJohn Levon if (oldsigned == newsigned) {
1401f5207b7SJohn Levon warning(insn->pos, "cast wasn't removed");
1411f5207b7SJohn Levon return;
1421f5207b7SJohn Levon }
1431f5207b7SJohn Levon warning(insn->pos, "cast changes sign");
1441f5207b7SJohn Levon }
1451f5207b7SJohn Levon }
1461f5207b7SJohn Levon
check_range_instruction(struct instruction * insn)1471f5207b7SJohn Levon static void check_range_instruction(struct instruction *insn)
1481f5207b7SJohn Levon {
1491f5207b7SJohn Levon warning(insn->pos, "value out of range");
1501f5207b7SJohn Levon }
1511f5207b7SJohn Levon
check_byte_count(struct instruction * insn,pseudo_t count)1521f5207b7SJohn Levon static void check_byte_count(struct instruction *insn, pseudo_t count)
1531f5207b7SJohn Levon {
1541f5207b7SJohn Levon if (!count)
1551f5207b7SJohn Levon return;
1561f5207b7SJohn Levon if (count->type == PSEUDO_VAL) {
1571f5207b7SJohn Levon unsigned long long val = count->value;
1581f5207b7SJohn Levon if (Wmemcpy_max_count && val > fmemcpy_max_count)
1591f5207b7SJohn Levon warning(insn->pos, "%s with byte count of %llu",
1601f5207b7SJohn Levon show_ident(insn->func->sym->ident), val);
1611f5207b7SJohn Levon return;
1621f5207b7SJohn Levon }
1631f5207b7SJohn Levon /* OK, we could try to do the range analysis here */
1641f5207b7SJohn Levon }
1651f5207b7SJohn Levon
argument(struct instruction * call,unsigned int argno)1661f5207b7SJohn Levon static pseudo_t argument(struct instruction *call, unsigned int argno)
1671f5207b7SJohn Levon {
1681f5207b7SJohn Levon pseudo_t args[8];
1691f5207b7SJohn Levon struct ptr_list *arg_list = (struct ptr_list *) call->arguments;
1701f5207b7SJohn Levon
1711f5207b7SJohn Levon argno--;
1721f5207b7SJohn Levon if (linearize_ptr_list(arg_list, (void *)args, 8) > argno)
1731f5207b7SJohn Levon return args[argno];
1741f5207b7SJohn Levon return NULL;
1751f5207b7SJohn Levon }
1761f5207b7SJohn Levon
check_memset(struct instruction * insn)1771f5207b7SJohn Levon static void check_memset(struct instruction *insn)
1781f5207b7SJohn Levon {
1791f5207b7SJohn Levon check_byte_count(insn, argument(insn, 3));
1801f5207b7SJohn Levon }
1811f5207b7SJohn Levon
1821f5207b7SJohn Levon #define check_memcpy check_memset
1831f5207b7SJohn Levon #define check_ctu check_memset
1841f5207b7SJohn Levon #define check_cfu check_memset
1851f5207b7SJohn Levon
1861f5207b7SJohn Levon struct checkfn {
1871f5207b7SJohn Levon struct ident *id;
1881f5207b7SJohn Levon void (*check)(struct instruction *insn);
1891f5207b7SJohn Levon };
1901f5207b7SJohn Levon
check_call_instruction(struct instruction * insn)1911f5207b7SJohn Levon static void check_call_instruction(struct instruction *insn)
1921f5207b7SJohn Levon {
1931f5207b7SJohn Levon pseudo_t fn = insn->func;
1941f5207b7SJohn Levon struct ident *ident;
1951f5207b7SJohn Levon static const struct checkfn check_fn[] = {
1961f5207b7SJohn Levon { &memset_ident, check_memset },
1971f5207b7SJohn Levon { &memcpy_ident, check_memcpy },
1981f5207b7SJohn Levon { ©_to_user_ident, check_ctu },
1991f5207b7SJohn Levon { ©_from_user_ident, check_cfu },
2001f5207b7SJohn Levon };
2011f5207b7SJohn Levon int i;
2021f5207b7SJohn Levon
2031f5207b7SJohn Levon if (fn->type != PSEUDO_SYM)
2041f5207b7SJohn Levon return;
2051f5207b7SJohn Levon ident = fn->sym->ident;
2061f5207b7SJohn Levon if (!ident)
2071f5207b7SJohn Levon return;
2081f5207b7SJohn Levon for (i = 0; i < ARRAY_SIZE(check_fn); i++) {
2091f5207b7SJohn Levon if (check_fn[i].id != ident)
2101f5207b7SJohn Levon continue;
2111f5207b7SJohn Levon check_fn[i].check(insn);
2121f5207b7SJohn Levon break;
2131f5207b7SJohn Levon }
2141f5207b7SJohn Levon }
2151f5207b7SJohn Levon
check_one_instruction(struct instruction * insn)2161f5207b7SJohn Levon static void check_one_instruction(struct instruction *insn)
2171f5207b7SJohn Levon {
2181f5207b7SJohn Levon switch (insn->opcode) {
219*c85f09ccSJohn Levon case OP_SEXT: case OP_ZEXT:
220*c85f09ccSJohn Levon case OP_TRUNC:
2211f5207b7SJohn Levon if (verbose)
2221f5207b7SJohn Levon check_cast_instruction(insn);
2231f5207b7SJohn Levon break;
2241f5207b7SJohn Levon case OP_RANGE:
2251f5207b7SJohn Levon check_range_instruction(insn);
2261f5207b7SJohn Levon break;
2271f5207b7SJohn Levon case OP_CALL:
2281f5207b7SJohn Levon check_call_instruction(insn);
2291f5207b7SJohn Levon break;
2301f5207b7SJohn Levon default:
2311f5207b7SJohn Levon break;
2321f5207b7SJohn Levon }
2331f5207b7SJohn Levon }
2341f5207b7SJohn Levon
check_bb_instructions(struct basic_block * bb)2351f5207b7SJohn Levon static void check_bb_instructions(struct basic_block *bb)
2361f5207b7SJohn Levon {
2371f5207b7SJohn Levon struct instruction *insn;
2381f5207b7SJohn Levon FOR_EACH_PTR(bb->insns, insn) {
2391f5207b7SJohn Levon if (!insn->bb)
2401f5207b7SJohn Levon continue;
2411f5207b7SJohn Levon check_one_instruction(insn);
2421f5207b7SJohn Levon } END_FOR_EACH_PTR(insn);
2431f5207b7SJohn Levon }
2441f5207b7SJohn Levon
check_instructions(struct entrypoint * ep)2451f5207b7SJohn Levon static void check_instructions(struct entrypoint *ep)
2461f5207b7SJohn Levon {
2471f5207b7SJohn Levon struct basic_block *bb;
2481f5207b7SJohn Levon FOR_EACH_PTR(ep->bbs, bb) {
249*c85f09ccSJohn Levon bb->context = -1;
2501f5207b7SJohn Levon check_bb_instructions(bb);
2511f5207b7SJohn Levon } END_FOR_EACH_PTR(bb);
2521f5207b7SJohn Levon }
2531f5207b7SJohn Levon
check_context(struct entrypoint * ep)2541f5207b7SJohn Levon static void check_context(struct entrypoint *ep)
2551f5207b7SJohn Levon {
2561f5207b7SJohn Levon struct symbol *sym = ep->name;
2571f5207b7SJohn Levon struct context *context;
2581f5207b7SJohn Levon unsigned int in_context = 0, out_context = 0;
2591f5207b7SJohn Levon
2601f5207b7SJohn Levon if (Wuninitialized && verbose && ep->entry->bb->needs) {
2611f5207b7SJohn Levon pseudo_t pseudo;
2621f5207b7SJohn Levon FOR_EACH_PTR(ep->entry->bb->needs, pseudo) {
2631f5207b7SJohn Levon if (pseudo->type != PSEUDO_ARG)
2641f5207b7SJohn Levon warning(sym->pos, "%s: possible uninitialized variable (%s)",
2651f5207b7SJohn Levon show_ident(sym->ident), show_pseudo(pseudo));
2661f5207b7SJohn Levon } END_FOR_EACH_PTR(pseudo);
2671f5207b7SJohn Levon }
2681f5207b7SJohn Levon
2691f5207b7SJohn Levon check_instructions(ep);
2701f5207b7SJohn Levon
2711f5207b7SJohn Levon FOR_EACH_PTR(sym->ctype.contexts, context) {
2721f5207b7SJohn Levon in_context += context->in;
2731f5207b7SJohn Levon out_context += context->out;
2741f5207b7SJohn Levon } END_FOR_EACH_PTR(context);
2751f5207b7SJohn Levon check_bb_context(ep, ep->entry->bb, in_context, out_context);
2761f5207b7SJohn Levon }
2771f5207b7SJohn Levon
278*c85f09ccSJohn Levon /* list_compound_symbol - symbol info for arrays, structures, unions */
list_compound_symbol(struct symbol * sym)279*c85f09ccSJohn Levon static void list_compound_symbol(struct symbol *sym)
280*c85f09ccSJohn Levon {
281*c85f09ccSJohn Levon struct symbol *base;
282*c85f09ccSJohn Levon
283*c85f09ccSJohn Levon /* Only show symbols that have a positive size */
284*c85f09ccSJohn Levon if (sym->bit_size <= 0)
285*c85f09ccSJohn Levon return;
286*c85f09ccSJohn Levon if (!sym->ctype.base_type)
287*c85f09ccSJohn Levon return;
288*c85f09ccSJohn Levon /* Don't show unnamed types */
289*c85f09ccSJohn Levon if (!sym->ident)
290*c85f09ccSJohn Levon return;
291*c85f09ccSJohn Levon
292*c85f09ccSJohn Levon if (sym->type == SYM_NODE)
293*c85f09ccSJohn Levon base = sym->ctype.base_type;
294*c85f09ccSJohn Levon else
295*c85f09ccSJohn Levon base = sym;
296*c85f09ccSJohn Levon switch (base->type) {
297*c85f09ccSJohn Levon case SYM_STRUCT: case SYM_UNION: case SYM_ARRAY:
298*c85f09ccSJohn Levon break;
299*c85f09ccSJohn Levon default:
300*c85f09ccSJohn Levon return;
301*c85f09ccSJohn Levon }
302*c85f09ccSJohn Levon
303*c85f09ccSJohn Levon info(sym->pos, "%s: compound size %u, alignment %lu",
304*c85f09ccSJohn Levon show_typename(sym),
305*c85f09ccSJohn Levon bits_to_bytes(sym->bit_size),
306*c85f09ccSJohn Levon sym->ctype.alignment);
307*c85f09ccSJohn Levon }
308*c85f09ccSJohn Levon
check_symbols(struct symbol_list * list)3091f5207b7SJohn Levon static void check_symbols(struct symbol_list *list)
3101f5207b7SJohn Levon {
3111f5207b7SJohn Levon struct symbol *sym;
3121f5207b7SJohn Levon
3131f5207b7SJohn Levon FOR_EACH_PTR(list, sym) {
3141f5207b7SJohn Levon struct entrypoint *ep;
3151f5207b7SJohn Levon
3161f5207b7SJohn Levon expand_symbol(sym);
3171f5207b7SJohn Levon ep = linearize_symbol(sym);
318*c85f09ccSJohn Levon if (ep && ep->entry) {
3191f5207b7SJohn Levon if (dbg_entry)
3201f5207b7SJohn Levon show_entry(ep);
3211f5207b7SJohn Levon
3221f5207b7SJohn Levon check_context(ep);
3231f5207b7SJohn Levon }
324*c85f09ccSJohn Levon if (dbg_compound)
325*c85f09ccSJohn Levon list_compound_symbol(sym);
3261f5207b7SJohn Levon } END_FOR_EACH_PTR(sym);
3271f5207b7SJohn Levon
3281f5207b7SJohn Levon if (Wsparse_error && die_if_error)
3291f5207b7SJohn Levon exit(1);
3301f5207b7SJohn Levon }
3311f5207b7SJohn Levon
main(int argc,char ** argv)3321f5207b7SJohn Levon int main(int argc, char **argv)
3331f5207b7SJohn Levon {
3341f5207b7SJohn Levon struct string_list *filelist = NULL;
3351f5207b7SJohn Levon char *file;
3361f5207b7SJohn Levon
337*c85f09ccSJohn Levon // by default ignore -o <file>
338*c85f09ccSJohn Levon do_output = 0;
339*c85f09ccSJohn Levon
3401f5207b7SJohn Levon // Expand, linearize and show it.
3411f5207b7SJohn Levon check_symbols(sparse_initialize(argc, argv, &filelist));
342*c85f09ccSJohn Levon FOR_EACH_PTR(filelist, file) {
3431f5207b7SJohn Levon check_symbols(sparse(file));
344*c85f09ccSJohn Levon } END_FOR_EACH_PTR(file);
3451f5207b7SJohn Levon
3461f5207b7SJohn Levon report_stats();
3471f5207b7SJohn Levon return 0;
3481f5207b7SJohn Levon }
349