Rename "check.c" to "sparse.c" to match program name; update .gitignore

Signed-off-by: Josh Triplett <josh@freedesktop.org>

1 files changed, 283 insertions, 0 deletions

diff --git a/sparse.c b/sparse.c
new file mode 100644
index 0000000..6c06988
--- /dev/null
+++ b/sparse.c
@@ -0,0 +1,283 @@
+/*
+ * Example trivial client program that uses the sparse library
+ * to tokenize, pre-process and parse a C file, and prints out
+ * the results.
+ *
+ * Copyright (C) 2003 Transmeta Corp.
+ *               2003-2004 Linus Torvalds
+ *
+ *  Licensed under the Open Software License version 1.1
+ */
+#include <stdarg.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include <unistd.h>
+#include <fcntl.h>
+
+#include "lib.h"
+#include "allocate.h"
+#include "token.h"
+#include "parse.h"
+#include "symbol.h"
+#include "expression.h"
+#include "linearize.h"
+
+static int context_increase(struct basic_block *bb, int entry)
+{
+	int sum = 0;
+	struct instruction *insn;
+
+	FOR_EACH_PTR(bb->insns, insn) {
+		int val;
+		if (insn->opcode != OP_CONTEXT)
+			continue;
+		val = insn->increment;
+		if (insn->check) {
+			int current = sum + entry;
+			if (!val) {
+				if (!current)
+					continue;
+			} else if (current >= val)
+				continue;
+			warning(insn->pos, "context check failure");
+			continue;
+		}
+		sum += val;
+	} END_FOR_EACH_PTR(insn);
+	return sum;
+}
+
+static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
+{
+	if (Wcontext) {
+		struct symbol *sym = ep->name;
+		warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
+	}
+	return -1;
+}
+
+static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
+
+static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
+{
+	struct instruction *insn;
+	struct basic_block *child;
+
+	insn = last_instruction(bb->insns);
+	if (!insn)
+		return 0;
+	if (insn->opcode == OP_RET)
+		return entry != exit ? imbalance(ep, bb, entry, exit, "wrong count at exit") : 0;
+
+	FOR_EACH_PTR(bb->children, child) {
+		if (check_bb_context(ep, child, entry, exit))
+			return -1;
+	} END_FOR_EACH_PTR(child);
+	return 0;
+}
+
+static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
+{
+	if (!bb)
+		return 0;
+	if (bb->context == entry)
+		return 0;
+
+	/* Now that's not good.. */
+	if (bb->context >= 0)
+		return imbalance(ep, bb, entry, bb->context, "different lock contexts for basic block");
+
+	bb->context = entry;
+	entry += context_increase(bb, entry);
+	if (entry < 0)
+		return imbalance(ep, bb, entry, exit, "unexpected unlock");
+
+	return check_children(ep, bb, entry, exit);
+}
+
+static void check_cast_instruction(struct instruction *insn)
+{
+	struct symbol *orig_type = insn->orig_type;
+	if (orig_type) {
+		int old = orig_type->bit_size;
+		int new = insn->size;
+		int oldsigned = (orig_type->ctype.modifiers & MOD_SIGNED) != 0;
+		int newsigned = insn->opcode == OP_SCAST;
+
+		if (new > old) {
+			if (oldsigned == newsigned)
+				return;
+			if (newsigned)
+				return;
+			warning(insn->pos, "cast loses sign");
+			return;
+		}
+		if (new < old) {
+			warning(insn->pos, "cast drops bits");
+			return;
+		}
+		if (oldsigned == newsigned) {
+			warning(insn->pos, "cast wasn't removed");
+			return;
+		}
+		warning(insn->pos, "cast changes sign");
+	}
+}
+
+static void check_range_instruction(struct instruction *insn)
+{
+	warning(insn->pos, "value out of range");
+}
+
+static void check_byte_count(struct instruction *insn, pseudo_t count)
+{
+	if (!count)
+		return;
+	if (count->type == PSEUDO_VAL) {
+		long long val = count->value;
+		if (val <= 0 || val > 100000)
+			warning(insn->pos, "%s with byte count of %lld",
+				show_ident(insn->func->sym->ident), val);
+		return;
+	}
+	/* Ok, we could try to do the range analysis here */
+}
+
+static pseudo_t argument(struct instruction *call, unsigned int argno)
+{
+	pseudo_t args[8];
+	struct ptr_list *arg_list = (struct ptr_list *) call->arguments;
+
+	argno--;
+	if (linearize_ptr_list(arg_list, (void *)args, 8) > argno)
+		return args[argno];
+	return NULL;
+}
+
+static void check_memset(struct instruction *insn)
+{
+	check_byte_count(insn, argument(insn, 3));
+}
+
+#define check_memcpy check_memset
+#define check_ctu check_memset
+#define check_cfu check_memset
+
+struct checkfn {
+	struct ident *id;
+	void (*check)(struct instruction *insn);
+};
+
+static void check_call_instruction(struct instruction *insn)
+{
+	pseudo_t fn = insn->func;
+	struct ident *ident;
+	static const struct checkfn check_fn[] = {
+		{ &memset_ident, check_memset },
+		{ &memcpy_ident, check_memcpy },
+		{ &copy_to_user_ident, check_ctu },
+		{ &copy_from_user_ident, check_cfu },
+	};
+	int i;
+
+	if (fn->type != PSEUDO_SYM)
+		return;
+	ident = fn->sym->ident;
+	if (!ident)
+		return;
+	for (i = 0; i < sizeof(check_fn)/sizeof(struct checkfn) ; i++) {
+		if (check_fn[i].id != ident)
+			continue;
+		check_fn[i].check(insn);
+		break;
+	}
+}
+
+static void check_one_instruction(struct instruction *insn)
+{
+	switch (insn->opcode) {
+	case OP_CAST: case OP_SCAST:
+		if (verbose)
+			check_cast_instruction(insn);
+		break;
+	case OP_RANGE:
+		check_range_instruction(insn);
+		break;
+	case OP_CALL:
+		check_call_instruction(insn);
+		break;
+	default:
+		break;
+	}
+}
+
+static void check_bb_instructions(struct basic_block *bb)
+{
+	struct instruction *insn;
+	FOR_EACH_PTR(bb->insns, insn) {
+		if (!insn->bb)
+			continue;
+		check_one_instruction(insn);
+	} END_FOR_EACH_PTR(insn);
+}
+
+static void check_instructions(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+	FOR_EACH_PTR(ep->bbs, bb) {
+		check_bb_instructions(bb);
+	} END_FOR_EACH_PTR(bb);
+}
+
+static void check_context(struct entrypoint *ep)
+{
+	struct symbol *sym = ep->name;
+	struct context *context;
+	unsigned int in_context = 0, out_context = 0;
+
+	if (Wuninitialized && verbose && ep->entry->bb->needs) {
+		pseudo_t pseudo;
+		FOR_EACH_PTR(ep->entry->bb->needs, pseudo) {
+			if (pseudo->type != PSEUDO_ARG)
+				warning(sym->pos, "%s: possible uninitialized variable (%s)",
+					show_ident(sym->ident), show_pseudo(pseudo));
+		} END_FOR_EACH_PTR(pseudo);
+	}
+
+	check_instructions(ep);
+
+	FOR_EACH_PTR(sym->ctype.contexts, context) {
+		in_context += context->in;
+		out_context += context->out;
+	} END_FOR_EACH_PTR(context);
+	check_bb_context(ep, ep->entry->bb, in_context, out_context);
+}
+
+static void check_symbols(struct symbol_list *list)
+{
+	struct symbol *sym;
+
+	FOR_EACH_PTR(list, sym) {
+		struct entrypoint *ep;
+
+		expand_symbol(sym);
+		ep = linearize_symbol(sym);
+		if (ep)
+			check_context(ep);
+	} END_FOR_EACH_PTR(sym);
+}
+
+int main(int argc, char **argv)
+{
+	struct string_list *filelist = NULL;
+	char *file;
+
+	// Expand, linearize and show it.
+	check_symbols(sparse_initialize(argc, argv, &filelist));
+	FOR_EACH_PTR_NOTAG(filelist, file) {
+		check_symbols(sparse(file));
+	} END_FOR_EACH_PTR_NOTAG(file);
+	return 0;
+}