[PATCH 5] Adding the NULL pointer checker.

[PATCH 5] Adding the NULL pointer checker.

[Christopher Li]

Changelog:
 - Using pseudo user list to find out the calling function.
   It doesn't scan instruction one by one any more.

This patch add the kmalloc null pointer checking. It also
try to track the double free as well. It knows a few kmalloc like
functions and kfree etc.

The interrupt checking is just a toy. Without cross function checking,
it is way too many false positive. 

Signed-off-by: Christopher Li<sparse@chrisli.org>

Index: sparse/blobhash.c
===================================================================
--- sparse.orig/blobhash.c	2007-01-16 11:13:28.000000000 -0800
+++ sparse/blobhash.c	2007-01-16 11:13:28.000000000 -0800
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2006 Christopher Li <sparse@chrisli.org>
+ * Copyright (C) 2003 Transmeta Corp.
+ *               2003 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"
+#include "storage.h"
+#include "checker.h"
+
+/*
+ * steal from tokenize.c 
+ */
+#define BLOB_HASH_BITS (13)
+#define BLOB_HASH_SIZE (1<<BLOB_HASH_BITS)
+#define BLOB_HASH_MASK (BLOB_HASH_SIZE-1)
+
+#define blob_hash_init(c)		(c)
+#define blob_hash_add(oldhash,c)	((oldhash)*11 + (c))
+#define blob_hash_end(hash)		((((hash) >> BLOB_HASH_BITS) + (hash)) & BLOB_HASH_MASK)
+
+ALLOCATOR(blob, "pseudo state blob");
+ALLOCATOR(bb_state, "basic block state");
+ALLOCATOR(state, "one state");
+
+
+static struct blob_list *blob_hash_table[BLOB_HASH_SIZE];
+
+static unsigned long blob_hash(const unsigned char *data, int len)
+{
+	unsigned long hash;
+	const unsigned char *p = data;
+
+	hash = blob_hash_init(0);
+	while (len--) {
+		unsigned int i = *p++;
+		hash = blob_hash_add(hash, i);
+	}
+	return blob_hash_end(hash);
+}
+
+struct blob *lookup_blob(const unsigned char *data, int len)
+{
+	struct blob_list *list = blob_hash_table[blob_hash(data, len)];
+	struct blob *blob;
+
+	FOR_EACH_PTR(list, blob) {
+		if (blob->len == len && !memcmp(blob->data, data, len))
+			return blob;
+	} END_FOR_EACH_PTR(blob);
+	return NULL;
+}
+
+struct blob *create_hashed_blob(const unsigned char *data, int len)
+{
+	struct blob_list **list = blob_hash_table + blob_hash(data, len);
+	struct blob *blob;
+	FOR_EACH_PTR(*list, blob) {
+		if (blob->len == len && !memcmp(blob->data, data, len))
+			return blob;
+	} END_FOR_EACH_PTR(blob);
+	blob = alloc_blob(len);
+	memcpy(blob->data, data, len);
+	add_blob(list, blob);
+	return blob;
+}
+
+void free_blob(void)
+{
+	int i;
+
+	for (i = 0; i < BLOB_HASH_SIZE; i++) {
+		free_ptr_list(blob_hash_table + i);
+	}
+	clear_blob_alloc();
+}
+
Index: sparse/unssa.h
===================================================================
Index: sparse/unssa.c
===================================================================
--- sparse.orig/unssa.c	2007-01-16 11:13:18.000000000 -0800
+++ sparse/unssa.c	2007-01-16 11:13:28.000000000 -0800
@@ -24,8 +24,8 @@
  */
 
 #include "lib.h"
-#include "linearize.h"
 #include "allocate.h"
+#include "linearize.h"
 #include <assert.h>
 
 
Index: sparse/flow.c
===================================================================
Index: sparse/ptrlist.h
===================================================================
--- sparse.orig/ptrlist.h	2007-01-16 11:13:18.000000000 -0800
+++ sparse/ptrlist.h	2007-01-16 11:13:28.000000000 -0800
@@ -45,6 +45,8 @@ extern void concat_ptr_list(struct ptr_l
 extern void __free_ptr_list(struct ptr_list **);
 extern int ptr_list_size(struct ptr_list *);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);
+extern int find_ptr_in_list(struct ptr_list* list, void *ptr);
+extern int find_ptr_index(struct ptr_list* list, void *ptr);
 
 /*
  * Hey, who said that you can't do overloading in C?
Index: sparse/Makefile
===================================================================
--- sparse.orig/Makefile	2007-01-16 11:13:18.000000000 -0800
+++ sparse/Makefile	2007-01-16 11:54:51.000000000 -0800
@@ -27,12 +27,13 @@ INST_PROGRAMS=sparse cgcc
 
 LIB_H=    token.h parse.h lib.h symbol.h scope.h expression.h target.h \
 	  linearize.h bitmap.h ident-list.h compat.h flow.h allocate.h \
-	  storage.h ptrlist.h dissect.h
+	  storage.h ptrlist.h dissect.h checker.h
 
 LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
 	  expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \
 	  sort.o allocate.o compat-$(OS).o ptrlist.o \
-	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
+	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o \
+	  blobhash.o check-nullptr.o check-interrupt.o
 
 LIB_FILE= libsparse.a
 SLIB_FILE= libsparse.so
@@ -131,6 +132,9 @@ example.o: $(LIB_H)
 storage.o: $(LIB_H)
 dissect.o: $(LIB_H)
 graph.o: $(LIB_H)
+blobstate.o: $(LIB_H)
+check-nullptr.o: $(LIB_H)
+check-interrupt.o: $(LIB_H)
 
 compat-linux.o: compat/strtold.c compat/mmap-blob.c \
 	$(LIB_H)
Index: sparse/checker.h
===================================================================
--- sparse.orig/checker.h	2007-01-16 11:13:28.000000000 -0800
+++ sparse/checker.h	2007-01-16 11:57:29.000000000 -0800
@@ -0,0 +1,108 @@
+#ifndef _CHECKER_H_
+#define _CHECKER_H_
+
+struct blob {
+	int len;
+	unsigned char data[0];
+};
+
+struct bb_state;
+
+DECLARE_PTR_LIST(blob_list, struct blob);
+
+struct bb_state {
+	unsigned long generation;
+	struct instruction_list *insns;	// instruction relate to state.
+	struct blob_list *cached_state;
+	struct instruction *branch;
+	unsigned noret:1;
+};
+
+struct state {
+	unsigned char *statep;
+	unsigned long value;
+};
+
+DECLARE_ALLOCATOR(blob);
+DECLARE_ALLOCATOR(bb_state);
+DECLARE_ALLOCATOR(state);
+DECLARE_PTR_LIST(state_list, struct state);
+
+struct blob *lookup_blob(const unsigned char *data, int len);
+struct blob *create_hashed_blob(const unsigned char *data, int len);
+
+static inline struct blob* alloc_blob(int len)
+{
+	struct blob *blob = __alloc_blob(len);
+	blob->len = len;
+	return blob;
+}
+
+static inline void add_blob(struct blob_list **list, struct blob *blob)
+{
+	add_ptr_list(list, blob);
+}
+
+static inline struct bb_state* alloc_bb_state(void)
+{
+	return __alloc_bb_state(0);
+}
+
+#define new_state(list, p, v)						\
+	do {								\
+		typeof(p) __p = p;					\
+		struct state *__state = __alloc_state(0);		\
+		__state->statep = __p;					\
+		__state->value = *__p;					\
+		*__p = (v);						\
+		add_ptr_list(list, __state);				\
+	} while (0)
+
+
+#define revert_state(type, list, size)					\
+	do {								\
+		struct state *__state;					\
+		struct ptr_list **__list = (struct ptr_list **)(list);	\
+		type *__p;						\
+		while (ptr_list_size(*__list) > (size)) {		\
+			__state = undo_ptr_list_last(__list);		\
+			__p = __state->statep;				\
+			*__p = (type)__state->value;			\
+			__free_state(__state);				\
+		}							\
+	} while (0)
+
+
+#define FOR_EACH_FUNC_CALL(p, i)				\
+	do {							\
+		struct pseudo_user *__pu_##i;			\
+		FOR_EACH_PTR((p)->users, __pu_##i) {		\
+			(i) = __pu_##i->insn;			\
+			if (!(i)->bb)				\
+				continue;			\
+			if ((i)->opcode != OP_CALL)		\
+				continue;			\
+			if (__pu_##i->userp != &(i)->func)	\
+				continue;			\
+
+#define END_FOR_EACH_FUNC_CALL(i)				\
+		} END_FOR_EACH_PTR(__pu_##i);			\
+	} while (0)
+
+static inline struct instruction *checker_instruction(struct instruction *insn, int opcode, pseudo_t src)
+{
+	struct instruction *new = __alloc_instruction(0);
+	new->opcode = opcode;
+	new->pos = insn->pos;
+	new->bb = insn->bb;
+	new->src = src;
+	new->offset = find_ptr_index((struct ptr_list *)insn->bb->insns, insn);
+	return new;
+}
+
+extern void init_check_null_ptr(void);
+extern void check_null_ptr(struct entrypoint *ep);
+extern void check_interrupt(struct entrypoint *ep);
+
+#endif
+
Index: sparse/token.h
===================================================================
Index: sparse/allocate.c
===================================================================
Index: sparse/simplify.c
===================================================================
Index: sparse/memops.c
===================================================================
Index: sparse/allocate.h
===================================================================
Index: sparse/expand.c
===================================================================
--- sparse.orig/expand.c	2007-01-16 11:13:18.000000000 -0800
+++ sparse/expand.c	2007-01-16 11:13:28.000000000 -0800
@@ -29,8 +29,8 @@
 /* Random cost numbers */
 #define SIDE_EFFECTS 10000	/* The expression has side effects */
 #define UNSAFE 100		/* The expression may be "infinitely costly" due to exceptions */
-#define SELECT_COST 20		/* Cut-off for turning a conditional into a select */
-#define BRANCH_COST 10		/* Cost of a conditional branch */
+#define SELECT_COST 0		/* Cut-off for turning a conditional into a select */
+#define BRANCH_COST 0		/* Cost of a conditional branch */
 
 static int expand_expression(struct expression *);
 static int expand_statement(struct statement *);
Index: sparse/ident-list.h
===================================================================
Index: sparse/lib.h
===================================================================
Index: sparse/sparse.c
===================================================================
--- sparse.orig/sparse.c	2007-01-16 11:13:18.000000000 -0800
+++ sparse/sparse.c	2007-01-16 11:13:28.000000000 -0800
@@ -23,6 +23,8 @@
 #include "symbol.h"
 #include "expression.h"
 #include "linearize.h"
+#include "storage.h"
+#include "checker.h"
 
 static int context_increase(struct basic_block *bb, int entry)
 {
@@ -170,29 +172,39 @@ struct checkfn {
 	void (*check)(struct instruction *insn);
 };
 
+static const struct checkfn* match_function(const struct checkfn* checklist, struct symbol *fn)
+{
+	struct ident *ident;
+	int i;
+
+	ident = fn->ident;
+	if (!ident)
+		return NULL;
+
+	for (i = 0; checklist[i].id; i++) {
+		if (checklist[i].id != ident)
+			continue;
+		return checklist + i;
+	}
+	return NULL;
+}
+
 static void check_call_instruction(struct instruction *insn)
 {
 	pseudo_t fn = insn->func;
-	struct ident *ident;
-	static const struct checkfn check_fn[] = {
+	static const struct checkfn *entry, check_fn[] = {
 		{ &memset_ident, check_memset },
 		{ &memcpy_ident, check_memcpy },
 		{ &copy_to_user_ident, check_ctu },
 		{ &copy_from_user_ident, check_cfu },
+		{ NULL },
 	};
-	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;
-	}
+	entry = match_function(check_fn, fn->sym);
+	if (entry)
+		entry->check(insn);
 }
 
 static void check_one_instruction(struct instruction *insn)
@@ -264,8 +276,11 @@ static void check_symbols(struct symbol_
 
 		expand_symbol(sym);
 		ep = linearize_symbol(sym);
-		if (ep)
+		if (ep) {
 			check_context(ep);
+			check_null_ptr(ep);
+			check_interrupt(ep);
+		}
 	} END_FOR_EACH_PTR(sym);
 }
 
@@ -276,6 +291,8 @@ int main(int argc, char **argv)
 
 	// Expand, linearize and show it.
 	check_symbols(sparse_initialize(argc, argv, &filelist));
+
+	init_check_null_ptr();
 	FOR_EACH_PTR_NOTAG(filelist, file) {
 		check_symbols(sparse(file));
 	} END_FOR_EACH_PTR_NOTAG(file);
Index: sparse/linearize.h
===================================================================
--- sparse.orig/linearize.h	2007-01-16 11:13:18.000000000 -0800
+++ sparse/linearize.h	2007-01-16 11:13:28.000000000 -0800
@@ -29,7 +29,9 @@ enum pseudo_type {
 
 struct pseudo {
 	int nr;
-	enum pseudo_type type;
+	enum pseudo_type type:8;
+	unsigned state_index:16;
+	unsigned tracking:1;
 	struct pseudo_user_list *users;
 	struct ident *ident;
 	union {
@@ -211,14 +213,19 @@ enum opcode {
 
 	/* Needed to translate SSA back to normal form */
 	OP_COPY,
+	OP_LAST,
 };
 
 struct basic_block_list;
 struct instruction_list;
+struct bb_state;
 
 struct basic_block {
 	struct position pos;
-	unsigned long generation;
+	union {
+		unsigned long generation;
+		struct bb_state *state;
+	};
 	int context;
 	struct entrypoint *ep;
 	struct basic_block_list *parents; /* sources */
Index: sparse/check-interrupt.c
===================================================================
--- sparse.orig/check-interrupt.c	2007-01-16 11:13:28.000000000 -0800
+++ sparse/check-interrupt.c	2007-01-16 11:13:28.000000000 -0800
@@ -0,0 +1,159 @@
+/*
+ * Copyright (C) 2006 Christopher Li <sparse@chrisli.org>
+ *
+ *  Licensed under the Open Software License version 1.1
+ */
+
+#include <stdio.h>
+#include <string.h>
+
+#include "lib.h"
+#include "allocate.h"
+#include "token.h"
+#include "parse.h"
+#include "symbol.h"
+#include "expression.h"
+#include "linearize.h"
+#include "storage.h"
+#include "checker.h"
+
+
+static unsigned char current;
+static struct blob *hashed_state;
+static struct state_list *state_stack = NULL;
+
+enum {
+	OP_CLI = OP_LAST,
+	OP_STI,
+	OP_RESTORE,
+};
+
+enum {
+	INTR_ENABLE,
+	INTR_DISABLE,
+};
+
+static inline void execute_enable(struct instruction *insn)
+{
+	if (current == INTR_ENABLE) {
+		warning(insn->pos, "checker function %s double enable",
+			show_ident(insn->bb->ep->name->ident));
+		return;
+	}
+	new_state(&state_stack, &current, INTR_ENABLE); 
+	hashed_state = NULL;
+}
+
+static inline void execute_disable(struct instruction *insn)
+{
+	if (current == INTR_DISABLE) {
+		warning(insn->pos, "checker function %s double ensable",
+			show_ident(insn->bb->ep->name->ident));
+		return;
+	}
+	new_state(&state_stack, &current, INTR_DISABLE); 
+	hashed_state = NULL;
+}
+
+static inline void execute_ret(struct instruction *insn)
+{
+	if (current == INTR_DISABLE)
+		warning(insn->pos, "checker funcion %s exit with interrupt disabled",
+			show_ident(insn->bb->ep->name->ident));
+}
+
+static void check_bb(struct basic_block *bb)
+{
+	struct bb_state *bbs = bb->state;
+	struct instruction *insn;
+	int stacksize = ptr_list_size((struct ptr_list*)state_stack);
+	struct basic_block *child;
+
+	if (bbs->generation)
+		return;
+
+	if (!hashed_state)
+		hashed_state = create_hashed_blob(&current, 1);
+
+	/*
+	 * Try to find out if we execute the same state before. If the state is
+	 * same, there is not point try to execute it again.
+	 */
+	if (find_ptr_in_list((struct ptr_list*)bbs->cached_state, hashed_state))
+		return;
+
+	add_ptr_list(&bbs->cached_state, hashed_state);
+
+	bbs->generation = 1;
+
+	FOR_EACH_PTR(bbs->insns, insn) {
+		switch (insn->opcode) {
+		case OP_CLI:
+			execute_disable(insn);
+			break;
+		case OP_STI:
+		case OP_RESTORE:
+			execute_enable(insn);
+			break;
+		case OP_RET:
+			execute_ret(insn);
+			break;
+		}
+	} END_FOR_EACH_PTR(insn);
+
+	if (bbs->noret)
+		goto exit_bb;
+
+		
+	FOR_EACH_PTR(bb->children, child) {
+		check_bb(child);
+	} END_FOR_EACH_PTR(child);
+
+exit_bb:
+	if (ptr_list_size((struct ptr_list*)state_stack) > stacksize) {
+		revert_state(unsigned char, &state_stack, stacksize);
+		hashed_state = NULL;
+	}
+	bbs->generation = 0;
+}
+
+static inline void scan_interrupt_insn(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+	struct instruction *insn;
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		struct bb_state *bbs = bb->state;
+		FOR_EACH_PTR(bb->insns, insn) {
+			if (!insn->bb)
+				continue;
+			if (insn->opcode == OP_RET) {
+				add_instruction(&bbs->insns, insn);
+				continue;
+			}
+			else if (insn->opcode != OP_ASM)
+				continue;
+			if (!strcmp(insn->string, "cli"))
+				add_instruction(&bbs->insns, checker_instruction(insn, OP_CLI, NULL));
+			else if (!strcmp(insn->string, "sti"))
+				add_instruction(&bbs->insns, checker_instruction(insn, OP_STI, NULL));
+			else if (!strcmp(insn->string, "pushl %0 ; popfl"))
+				add_instruction(&bbs->insns, checker_instruction(insn, OP_RESTORE, NULL));
+		} END_FOR_EACH_PTR(insn);
+	} END_FOR_EACH_PTR(bb);
+}
+
+void check_interrupt(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		bb->state = alloc_bb_state();
+	} END_FOR_EACH_PTR(bb);
+
+	current = INTR_ENABLE;
+	hashed_state = NULL;
+	scan_interrupt_insn(ep);
+	check_bb(ep->entry->bb);
+}
+
Index: sparse/storage.h
===================================================================
Index: sparse/check-nullptr.c
===================================================================
--- sparse.orig/check-nullptr.c	2007-01-16 11:13:28.000000000 -0800
+++ sparse/check-nullptr.c	2007-01-16 11:57:14.000000000 -0800
@@ -0,0 +1,297 @@
+/*
+ * Copyright (C) 2006 Christopher Li <sparse@chrisli.org>
+ *
+ *  Licensed under the Open Software License version 1.1
+ */
+
+#include <stdio.h>
+
+#include "lib.h"
+#include "allocate.h"
+#include "token.h"
+#include "parse.h"
+#include "symbol.h"
+#include "expression.h"
+#include "linearize.h"
+#include "storage.h"
+#include "checker.h"
+
+
+static int state_count = 0;
+static struct ptr_list *malloc_ident_list = NULL;
+static struct ptr_list *free_ident_list = NULL;
+static struct ptr_list *noret_ident_list = NULL;
+
+static struct blob *current;
+static struct blob *hashed_state;
+static struct state_list *state_stack;
+static void check_bb(struct basic_block *bb);
+
+#define alloc_state() alloc_blob(state_count)
+#define reg_state(pseudo) ((current)->data[pseudo->state_index])
+
+#define PTR_NULL		1
+#define PTR_NOTNULL		2
+#define PTR_FREE		4
+
+enum {
+	OP_DEF_PTR = OP_LAST,
+	OP_USE_PTR,
+	OP_FREE_PTR
+};
+
+static int cmp_insn_pos(const void *a, const void *b)
+{
+	int a1 = ((struct instruction *)a)->offset, b1 = ((struct instruction *)b)->offset;
+	if (a1 == b1)
+		return 0;
+	return a1 > b1 ? 1 : -1;
+}
+
+static void check_bb_cond(struct basic_block *bb, pseudo_t cond, unsigned value)
+{
+	new_state(&state_stack, &reg_state(cond), value);
+	hashed_state = NULL;
+	check_bb(bb);
+}
+
+
+static inline void execute_pointer_define(struct instruction *insn)
+{
+	new_state(&state_stack, &reg_state(insn->src), PTR_NULL | PTR_NOTNULL); 
+	hashed_state = NULL;
+}
+
+static inline void execute_pointer_usage(struct instruction *insn)
+{
+	if (reg_state(insn->src) & PTR_NULL)
+		warning(insn->pos, "funcion %s possible using NULL pointer",
+			show_ident(insn->bb->ep->name->ident));
+	if (reg_state(insn->src) & PTR_FREE)
+		warning(insn->pos, "funcion %s possible using pointer after free",
+			show_ident(insn->bb->ep->name->ident));
+}
+
+static inline void execute_pointer_free(struct instruction *insn)
+{
+	if (reg_state(insn->src) & PTR_FREE)
+		warning(insn->pos, "funcion %s possible double free pointer",
+			show_ident(insn->bb->ep->name->ident));
+	new_state(&state_stack, &reg_state(insn->src), reg_state(insn->src) | PTR_FREE); 
+	hashed_state = NULL;
+
+}
+static void check_bb(struct basic_block *bb)
+{
+	struct bb_state *bbs = bb->state;
+	struct instruction *insn;
+	int stacksize = ptr_list_size((struct ptr_list*)state_stack);
+
+	if (bbs->generation)
+		return;
+
+	if (!hashed_state)
+		hashed_state = create_hashed_blob(current->data, state_count);
+
+	/*
+	 * Try to find out if we execute the same state before. If the state is
+	 * same, there is not point try to execute it again.
+	 */
+	if (find_ptr_in_list((struct ptr_list*)bbs->cached_state, hashed_state))
+		return;
+
+	add_ptr_list(&bbs->cached_state, hashed_state);
+
+	bbs->generation = 1;
+
+	FOR_EACH_PTR(bbs->insns, insn) {
+		switch (insn->opcode) {
+		case OP_DEF_PTR:
+			execute_pointer_define(insn);
+			break;
+		case OP_USE_PTR:
+			execute_pointer_usage(insn);
+			break;
+		case OP_FREE_PTR:
+			execute_pointer_free(insn);
+			break;
+		}
+	} END_FOR_EACH_PTR(insn);
+
+	if (bbs->noret)
+		goto exit_bb;
+
+	if (bbs->branch) {
+		struct instruction *br = bbs->branch;
+		unsigned char orig = reg_state(br->cond);
+		check_bb_cond(br->bb_true, br->cond, orig & ~PTR_NULL);
+		check_bb_cond(br->bb_false, br->cond, orig & ~PTR_NOTNULL);
+	} else {
+		struct basic_block *child;
+		
+		FOR_EACH_PTR(bb->children, child) {
+			check_bb(child);
+		} END_FOR_EACH_PTR(child);
+	}
+
+exit_bb:
+	if (ptr_list_size((struct ptr_list*)state_stack) > stacksize) {
+		revert_state(unsigned char, &state_stack, stacksize);
+		hashed_state = NULL;
+	}
+	bbs->generation = 0;
+}
+
+static inline int match_call_function(struct instruction *insn, struct ptr_list *list)
+{
+	struct ident *ident;
+	pseudo_t fn;
+
+	if (insn->opcode != OP_CALL)
+		return 0;
+	fn = insn->func;
+	if (fn->type != PSEUDO_SYM)
+		return 0;
+	ident = fn->sym->ident;
+	if (!ident)
+		return 0;
+	return find_ptr_in_list(list, ident);
+}
+
+static void follow_pointer_usage(struct instruction *insn, pseudo_t pseudo, int index)
+{
+	struct pseudo_user *pu;
+
+	pseudo->tracking = 1;
+	pseudo->state_index = index;
+
+	FOR_EACH_PTR(pseudo->users, pu) {
+		struct instruction *useri = pu->insn;
+		struct basic_block *bb = useri->bb;
+		struct bb_state *bb_state;
+		if (!bb)
+			continue;
+		bb_state = bb->state;
+
+		switch(useri->opcode) {
+		case OP_CAST: case OP_SCAST: case OP_PTRCAST:
+			/* cast a pointer does not change the pointer state, it is just alias */
+			follow_pointer_usage(useri, useri->target, index);
+			break;
+		case OP_STORE:
+			if (pseudo == useri->src) {
+				struct instruction *use = checker_instruction(useri, OP_USE_PTR,
+									      pseudo);
+				add_instruction(&bb_state->insns, use);
+			}
+			break;
+		case OP_CALL:
+			if (match_call_function(useri, free_ident_list)) {
+				struct instruction *fr = checker_instruction(useri, OP_FREE_PTR,
+									      pseudo);
+				add_instruction(&bb_state->insns, fr);
+			}
+			break;
+		case OP_BR:
+			bb_state->branch = useri;
+			break;
+ 		case OP_SWITCH:
+			warning(insn->pos, "switch on pointer not implemented\n");
+			break;
+		}
+	} END_FOR_EACH_PTR(pu);
+}
+		
+static inline void scan_pointer_define(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+	struct instruction *insn;
+	pseudo_t pseudo;
+
+	FOR_EACH_PTR(ep->accesses, pseudo) {
+		struct ident *ident = pseudo->sym->ident;
+		if (!ident)
+			continue;
+		if (find_ptr_in_list(noret_ident_list, ident)) {
+			FOR_EACH_FUNC_CALL(pseudo, insn) {
+				insn->bb->state->noret = 1;
+			} END_FOR_EACH_FUNC_CALL(insn);
+		}
+		if (find_ptr_in_list(malloc_ident_list, ident)) {
+			FOR_EACH_FUNC_CALL(pseudo, insn) {
+				struct instruction *def = checker_instruction(insn, OP_DEF_PTR, insn->target);
+				add_instruction(&insn->bb->state->insns, def);
+				follow_pointer_usage(insn, insn->target, state_count++);
+			} END_FOR_EACH_FUNC_CALL(insn);
+		}
+		
+	} END_FOR_EACH_PTR(pseudo);
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		sort_list((struct ptr_list **)&bb->state->insns, cmp_insn_pos);
+	} END_FOR_EACH_PTR(bb);
+}
+
+void check_null_ptr(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+
+	state_count = 0;
+	
+	FOR_EACH_PTR(ep->bbs, bb) {
+		bb->state = alloc_bb_state();
+	} END_FOR_EACH_PTR(bb);
+
+	scan_pointer_define(ep);
+	current = alloc_state();
+	check_bb(ep->entry->bb);
+}
+
+void init_check_null_ptr(void)
+{
+	static const char *malloc_name[] = {
+		"malloc",
+		"__kmalloc",
+		"__kmalloc_node",
+		"__kzalloc",
+		"kmem_cache_alloc",
+		"kmem_cache_zalloc",
+		"kmem_cache_alloc_node",
+		"vmalloc",
+		"vmalloc_user",
+		"vmalloc_node",
+		"vmalloc_32",
+		"vmalloc_32_user",
+		"__vmalloc",
+		NULL,
+	};
+	static const char *free_name[] = {
+		"free",
+		"kfree",
+		"kmem_cache_free",
+		"vfree",
+		NULL,
+	};
+	static const char *noret[] = {
+		"panic",
+		NULL,
+	};
+	int i;
+
+	for (i = 0; malloc_name[i]; i++) {
+		void* id = (void*) built_in_ident(malloc_name[i]);
+		add_ptr_list(&malloc_ident_list, id);
+	}
+
+	for (i = 0; free_name[i]; i++) {
+		void* id = (void*) built_in_ident(free_name[i]);
+		add_ptr_list(&free_ident_list, id);
+	}
+
+	for (i = 0; noret[i]; i++) {
+		void* id = (void*) built_in_ident(noret[i]);
+		add_ptr_list(&noret_ident_list, id);
+	}
+
+}
+
Index: sparse/linearize.c
===================================================================
Index: sparse/ptrlist.c
===================================================================
--- sparse.orig/ptrlist.c	2007-01-16 11:13:18.000000000 -0800
+++ sparse/ptrlist.c	2007-01-16 11:13:28.000000000 -0800
@@ -243,3 +243,29 @@ void __free_ptr_list(struct ptr_list **l
 
 	*listp = NULL;
 }
+
+int find_ptr_in_list(struct ptr_list* list, void *ptr)
+{
+	void *p;
+	FOR_EACH_PTR(list, p) {
+		if (p == ptr)
+			return 1;
+	} END_FOR_EACH_PTR(p);
+	return 0;
+}
+
+int find_ptr_index(struct ptr_list* list, void *ptr)
+{
+	void *p;
+	int i = 0;
+	FOR_EACH_PTR(list, p) {
+		if (p == ptr)
+			return i;
+		i++;
+	} END_FOR_EACH_PTR(p);
+	return -1;
+}
+
+
+
+

Re: [PATCH 5] Adding the NULL pointer checker.

[Christopher Li]

Oops, this should be [PATCH 6] instead.

Chris

On Tue, Jan 16, 2007 at 06:39:18PM -0800, Christopher Li wrote:
> 
> Changelog:
>  - Using pseudo user list to find out the calling function.
>    It doesn't scan instruction one by one any more.
> 
> This patch add the kmalloc null pointer checking. It also
> try to track the double free as well. It knows a few kmalloc like
> functions and kfree etc.
> 
> The interrupt checking is just a toy. Without cross function checking,
> it is way too many false positive. 
> 
> Signed-off-by: Christopher Li<sparse@chrisli.org>
> 

Re: [PATCH 5] Adding the NULL pointer checker.

[Josh Triplett]

[-- Attachment #1: Type: text/plain, Size: 7089 bytes --]

Somehow I managed to compose and not send these comments; sorry.

Christopher Li wrote:
> This patch add the kmalloc null pointer checking. It also
> try to track the double free as well. It knows a few kmalloc like
> functions and kfree etc.

Overall, this patch looks good, and I really like the idea of doing malloc
checking with Sparse.  I have a few comments, interspersed below.

The main issue, however: I can't seem to get it to generate any warnings.
I've tried running it on the following program, and it produces nothing:

#include <stdlib.h>
int main(int argc, char *argv[])
{
	int *i = malloc(sizeof(int));
	return *i;
}

Shouldn't this program provoke some warnings?  And could you supply some
test code which does provoke warnings?

Also, you need a new warning switch to control each of these two checks.

> The interrupt checking is just a toy. Without cross function checking,
> it is way too many false positive. 

I don't mind including it in an early stage, defaulting to off.

> --- sparse.orig/checker.h	2007-01-16 11:13:28.000000000 -0800
> +++ sparse/checker.h	2007-01-16 11:57:29.000000000 -0800
> @@ -0,0 +1,108 @@
> +#ifndef _CHECKER_H_
> +#define _CHECKER_H_
> +
> +struct blob {
> +	int len;

size_t len, please.

> +	unsigned char data[0];
> +};
[...]
> --- sparse.orig/expand.c	2007-01-16 11:13:18.000000000 -0800
> +++ sparse/expand.c	2007-01-16 11:13:28.000000000 -0800
> @@ -29,8 +29,8 @@
>  /* Random cost numbers */
>  #define SIDE_EFFECTS 10000	/* The expression has side effects */
>  #define UNSAFE 100		/* The expression may be "infinitely costly" due to exceptions */
> -#define SELECT_COST 20		/* Cut-off for turning a conditional into a select */
> -#define BRANCH_COST 10		/* Cost of a conditional branch */
> +#define SELECT_COST 0		/* Cut-off for turning a conditional into a select */
> +#define BRANCH_COST 0		/* Cost of a conditional branch */

OK, I *think* that won't cause any harm.

> --- sparse.orig/sparse.c	2007-01-16 11:13:18.000000000 -0800
> +++ sparse/sparse.c	2007-01-16 11:13:28.000000000 -0800
>  };
[...]
>  static void check_call_instruction(struct instruction *insn)
>  {
>  	pseudo_t fn = insn->func;
> -	struct ident *ident;
> -	static const struct checkfn check_fn[] = {
> +	static const struct checkfn *entry, check_fn[] = {
>  		{ &memset_ident, check_memset },
>  		{ &memcpy_ident, check_memcpy },
>  		{ &copy_to_user_ident, check_ctu },
>  		{ &copy_from_user_ident, check_cfu },
> +		{ NULL },
>  	};
> -	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;
> -	}
> +	entry = match_function(check_fn, fn->sym);
> +	if (entry)
> +		entry->check(insn);
>  }

Why this change, to use a NULL-terminated iteration rather than a counted
iteration?  I don't see the benefit.

> @@ -211,14 +213,19 @@ enum opcode {
>  
>  	/* Needed to translate SSA back to normal form */
>  	OP_COPY,
> +	OP_LAST,
>  };

Hmmm...

> --- sparse.orig/check-interrupt.c	2007-01-16 11:13:28.000000000 -0800
> +++ sparse/check-interrupt.c	2007-01-16 11:13:28.000000000 -0800
[...]
> +enum {
> +	OP_CLI = OP_LAST,
> +	OP_STI,
> +	OP_RESTORE,
> +};

Ouch.  This will break if anything else attempts to extend the opcode list
in the same way.

Have you considered attempting to express interrupts as another form of
context?  Now that the basic framework for multiple types of context exists,
perhaps you could treat interrupts as another kind of context?

> +static inline void scan_interrupt_insn(struct entrypoint *ep)
> +{
> +	struct basic_block *bb;
> +	struct instruction *insn;
> +
> +	FOR_EACH_PTR(ep->bbs, bb) {
> +		struct bb_state *bbs = bb->state;
> +		FOR_EACH_PTR(bb->insns, insn) {
> +			if (!insn->bb)
> +				continue;
> +			if (insn->opcode == OP_RET) {
> +				add_instruction(&bbs->insns, insn);
> +				continue;
> +			}
> +			else if (insn->opcode != OP_ASM)
> +				continue;
> +			if (!strcmp(insn->string, "cli"))
> +				add_instruction(&bbs->insns, checker_instruction(insn, OP_CLI, NULL));
> +			else if (!strcmp(insn->string, "sti"))
> +				add_instruction(&bbs->insns, checker_instruction(insn, OP_STI, NULL));
> +			else if (!strcmp(insn->string, "pushl %0 ; popfl"))
> +				add_instruction(&bbs->insns, checker_instruction(insn, OP_RESTORE, NULL));

Ouch.  x86-specific, and specific to the exact strings from the Linux inline
assembly.

We really need the metalanguage part of Engler's paper that you referenced.
This kind of thing seems reasonable for random scripts written to check
particular problems and interpreted by Sparse, but not for code going into
Sparse itself.

Also, modifying the instructions in bbs seems like it would conflict with the
use of other checkers, due to the enum collision described above.

[...]
> +enum {
> +	OP_DEF_PTR = OP_LAST,
> +	OP_USE_PTR,
> +	OP_FREE_PTR
> +};

Same problem as above.

> +static inline void execute_pointer_usage(struct instruction *insn)
> +{
> +	if (reg_state(insn->src) & PTR_NULL)
> +		warning(insn->pos, "funcion %s possible using NULL pointer",
> +			show_ident(insn->bb->ep->name->ident));

s/funcion/function/; s/possible/possibly/.

> +	if (reg_state(insn->src) & PTR_FREE)
> +		warning(insn->pos, "funcion %s possible using pointer after free",
> +			show_ident(insn->bb->ep->name->ident));

Likewise.


> +static inline void execute_pointer_free(struct instruction *insn)
> +{
> +	if (reg_state(insn->src) & PTR_FREE)
> +		warning(insn->pos, "funcion %s possible double free pointer",
> +			show_ident(insn->bb->ep->name->ident));

Likewise.

> +	if (bbs->branch) {
> +		struct instruction *br = bbs->branch;
> +		unsigned char orig = reg_state(br->cond);
> +		check_bb_cond(br->bb_true, br->cond, orig & ~PTR_NULL);
> +		check_bb_cond(br->bb_false, br->cond, orig & ~PTR_NOTNULL);

*Awesome*.

Something like this might work for conditional locking primitives, too.

> +void init_check_null_ptr(void)
> +{
> +	static const char *malloc_name[] = {
> +		"malloc",
> +		"__kmalloc",
> +		"__kmalloc_node",
> +		"__kzalloc",
> +		"kmem_cache_alloc",
> +		"kmem_cache_zalloc",
> +		"kmem_cache_alloc_node",
> +		"vmalloc",
> +		"vmalloc_user",
> +		"vmalloc_node",
> +		"vmalloc_32",
> +		"vmalloc_32_user",
> +		"__vmalloc",
> +		NULL,
> +	};
> +	static const char *free_name[] = {
> +		"free",
> +		"kfree",
> +		"kmem_cache_free",
> +		"vfree",
> +		NULL,
> +	};

Idea for future work (not for this patch): we might want to make sure that
memory allocated with a given malloc gets freed with a given free.

> +	static const char *noret[] = {
> +		"panic",
> +		NULL,
> +	};

We already have __attribute__((noreturn)); please use that rather than
matching against a list here.

- Josh Triplett


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: [PATCH 5] Adding the NULL pointer checker.

[Chris Li]

> > --- sparse.orig/expand.c      2007-01-16 11:13:18.000000000 -0800
> > +++ sparse/expand.c   2007-01-16 11:13:28.000000000 -0800
> > -#define SELECT_COST 20               /* Cut-off for turning a conditional into a select */
> > -#define BRANCH_COST 10               /* Cost of a conditional branch */
> > +#define SELECT_COST 0                /* Cut-off for turning a conditional into a select */
> > +#define BRANCH_COST 0                /* Cost of a conditional branch */
>
> OK, I *think* that won't cause any harm.

Linus, any words here? I have a vague impression that it has some thing to
do with simplifying phi usage, but I am not sure what is the real side effect.

Any way, the back ends should be able to do this transform themselves if they
need to.

> Overall, this patch looks good, and I really like the idea of doing malloc
> checking with Sparse.  I have a few comments, interspersed below.

Thanks for the review and applying my other patches. I am going to
update the null-ptr  checker patch.

>
> The main issue, however: I can't seem to get it to generate any warnings.
> I've tried running it on the following program, and it produces nothing:
>
> #include <stdlib.h>
> int main(int argc, char *argv[])
> {
>         int *i = malloc(sizeof(int));
>         return *i;
> }
>
> Shouldn't this program provoke some warnings?  And could you supply some
> test code which does provoke warnings?
>
Oops, I forget to look at the pointer load case.

The following patch should fix it. I can add my test case to a patch as well.
It should be nice to have some regression test suit.

--- .pc/state-rewrite-3.quiltsave/check-nullptr.c       2007-01-28
17:21:14.000000000 -0800
+++ check-nullptr.c     2007-01-28 17:27:53.000000000 -0800
@@ -179,6 +179,7 @@ static void follow_pointer_usage(struct
                        follow_pointer_usage(useri, useri->target, index);
                        break;
                case OP_STORE:
+               case OP_LOAD:
                        if (pseudo == useri->src) {
                                struct instruction *use =
checker_instruction(useri, OP_USE_PTR,

       pseudo);


>
> > The interrupt checking is just a toy. Without cross function checking,
> > it is way too many false positive.
>
> I don't mind including it in an early stage, defaulting to off.

Just as you said in the later part of the comment, the interrupt checking is
not quite ready yet.

>
> > --- sparse.orig/checker.h     2007-01-16 11:13:28.000000000 -0800
> > +++ sparse/checker.h  2007-01-16 11:57:29.000000000 -0800
> > @@ -0,0 +1,108 @@
> > +#ifndef _CHECKER_H_
> > +#define _CHECKER_H_
> > +
> > +struct blob {
> > +     int len;
>
> size_t len, please.

I can change it to unsigned int, just to consistent with the allocation code.
But I think size_t is over kill here because blob has  the same limitation
as the allocation code. The size can't be bigger than the allocation chunk
size, which is 32K right now. It is wrong to use really big object any way.

>
> > +     unsigned char data[0];
> > +};
> [...]
> > --- sparse.orig/expand.c      2007-01-16 11:13:18.000000000 -0800
>
> Why this change, to use a NULL-terminated iteration rather than a counted
> iteration?  I don't see the benefit.

That is should be cleaned up. I used to add my function match code here.

>
> > @@ -211,14 +213,19 @@ enum opcode {
> >
> >       /* Needed to translate SSA back to normal form */
> >       OP_COPY,
> > +     OP_LAST,
> >  };
>
> Hmmm...
>
> > --- sparse.orig/check-interrupt.c     2007-01-16 11:13:28.000000000 -0800
> > +++ sparse/check-interrupt.c  2007-01-16 11:13:28.000000000 -0800
> [...]
> > +enum {
> > +     OP_CLI = OP_LAST,
> > +     OP_STI,
> > +     OP_RESTORE,
> > +};
>
> Ouch.  This will break if anything else attempts to extend the opcode list
> in the same way.

Nope, this is checker specific opcode, which is *private* to the
checker. Checker
does not modify the bb->insn list. These opcode is generated in the
private checker
struct.

If anything attempts to extend the opcode list, it is likely a backend,
e.g. the x86 back end.

The checker don't need to know any thing about x86 back end specific
instruction. If it really do, then the check can use the last opcode of x86
and extend that.

If you think private opcode is not fine, please explain why it will break
other stuff.

>
> Have you considered attempting to express interrupts as another form of
> context?  Now that the basic framework for multiple types of context exists,
> perhaps you could treat interrupts as another kind of context?

Yes, they can. That has been considered. But it need to modify the linux code
to add context into interrupt related functions. I try not to modify
the checking
source code in spirit of the Stanford checker.

I am leaning towards adding annotation information for inline functions
so the checker can find out which inline function has been called.

>
> > +static inline void scan_interrupt_insn(struct entrypoint *ep)
> > +{
> > +     struct basic_block *bb;
> > +     struct instruction *insn;
> > +
> > +     FOR_EACH_PTR(ep->bbs, bb) {
> > +             struct bb_state *bbs = bb->state;
> > +             FOR_EACH_PTR(bb->insns, insn) {
> > +                     if (!insn->bb)
> > +                             continue;
> > +                     if (insn->opcode == OP_RET) {
> > +                             add_instruction(&bbs->insns, insn);
> > +                             continue;
> > +                     }
> > +                     else if (insn->opcode != OP_ASM)
> > +                             continue;
> > +                     if (!strcmp(insn->string, "cli"))
> > +                             add_instruction(&bbs->insns, checker_instruction(insn, OP_CLI, NULL));
> > +                     else if (!strcmp(insn->string, "sti"))
> > +                             add_instruction(&bbs->insns, checker_instruction(insn, OP_STI, NULL));
> > +                     else if (!strcmp(insn->string, "pushl %0 ; popfl"))
> > +                             add_instruction(&bbs->insns, checker_instruction(insn, OP_RESTORE, NULL));
>
> Ouch.  x86-specific, and specific to the exact strings from the Linux inline
> assembly.
>
> We really need the metalanguage part of Engler's paper that you referenced.
> This kind of thing seems reasonable for random scripts written to check
> particular problems and interpreted by Sparse, but not for code going into
> Sparse itself.

As I said, the interrupt checking is a prove of concept. It is a demo for
checking state not bind to a specific pseudo.

>
> Also, modifying the instructions in bbs seems like it would conflict with the
> use of other checkers, due to the enum collision described above.

Why? bbs is private checker state information. Each checker will initialize its
own bbs pointer. It is up to the checker how to store information there. Again,
the bbs->insns is different from the bb->insns. It is the checker instruction.
Consider checker as a lower level back end.

About the metalanguage, I don't think we need it right now. The code here
try to find out the caller for "sti" and "cli". We still need to write
the matching
code in metalanguage, having the metalanguage does not magically solve the
problem. Maintain and debug code generate by such a metalanguage is going
to be painful. You are still going to know the internal of metalanguage to be
able to debug it.

I think there is benefit for writing checking in pure C. Each checker
is its own module. I think the example here is simple enough that we can have
the whole execution engine inside the checker. It runs faster than those call
back based trigger. It is easier to debug the code.

Maintaining the metalanguage is a lot of over head. It is not some thing
I plan to do any time soon. It add a lot of complexity as well.

> > +static inline void execute_pointer_usage(struct instruction *insn)
> > +{
> > +     if (reg_state(insn->src) & PTR_NULL)
> > +             warning(insn->pos, "funcion %s possible using NULL pointer",
> > +                     show_ident(insn->bb->ep->name->ident));
>
> s/funcion/function/; s/possible/possibly/.

Thanks for catching that.

> Idea for future work (not for this patch): we might want to make sure that
> memory allocated with a given malloc gets freed with a given free.

It has been considered. It should be a later feature.

>
> > +     static const char *noret[] = {
> > +             "panic",
> > +             NULL,
> > +     };
>
> We already have __attribute__((noreturn)); please use that rather than
> matching against a list here.

I wish I can used that as well. But it is definitely a different patch to fix
function attribute parsing. It is getting very hairy.

Chris

Re: [PATCH 5] Adding the NULL pointer checker.

[Linus Torvalds]

On Mon, 29 Jan 2007, Chris Li wrote:

> > > --- sparse.orig/expand.c      2007-01-16 11:13:18.000000000 -0800
> > > +++ sparse/expand.c   2007-01-16 11:13:28.000000000 -0800
> > > -#define SELECT_COST 20               /* Cut-off for turning a conditional
> > into a select */
> > > -#define BRANCH_COST 10               /* Cost of a conditional branch */
> > > +#define SELECT_COST 0                /* Cut-off for turning a conditional
> > into a select */
> > > +#define BRANCH_COST 0                /* Cost of a conditional branch */
> > 
> > OK, I *think* that won't cause any harm.
> 
> Linus, any words here? I have a vague impression that it has some thing to
> do with simplifying phi usage, but I am not sure what is the real side effect.

I just think the old costs are likely more realistic, but they were pulled 
totally out of my *ss. 

If it's more convenient to set them to zero, go wild. No deep meaning.

		Linus