Skip to contentSkip to conversation

adding the null pointer checking

RFC PATCH New Christopher Li 1 participant 1 message Dec 28, 2006

Subsystems (2)
lore
Share & tools
lore

Christopher Li

author maintainer
#0 lore raw

RFC PATCH 4/4 adding the null pointer checking

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.

BTW, I disable the branch optimization in expand stage because this type of checking works best when different state follow different path.

Not a real patch submitting, I would love to heard some comment though.

Chris

blobhash.c +92 -0
Index: sparse/blobhash.c
===================================================================
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2006 Christopher Li <[email protected]>
+ * 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
===================================================================

unssa.c +1 -1
Index: sparse/unssa.c
===================================================================
@@ -24,8 +24,8 @@
  */
 
 #include "lib.h"
-#include "linearize.h"
 #include "allocate.h"
+#include "linearize.h"
 #include <assert.h>
 
 

Index: sparse/flow.c
===================================================================

ptrlist.h +2 -0
Index: sparse/ptrlist.h
===================================================================
@@ -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?
Makefile +6 -2
Index: sparse/Makefile
===================================================================
@@ -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)
checker.h +92 -0

92 lines not on this page · raw message

Index: sparse/token.h
===================================================================
Index: sparse/allocate.c
===================================================================
Index: sparse/simplify.c
===================================================================
Index: sparse/memops.c
===================================================================
Index: sparse/allocate.h
===================================================================

expand.c +2 -2
Index: sparse/expand.c
===================================================================
@@ -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
===================================================================

sparse.c +30 -13

79 lines not on this page · raw message

linearize.h +9 -2
Index: sparse/linearize.h
===================================================================
@@ -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 */
check-interrupt.c +159 -0

159 lines not on this page · raw message

Index: sparse/storage.h
===================================================================

check-nullptr.c +292 -0

292 lines not on this page · raw message

Index: sparse/linearize.c
===================================================================

ptrlist.c +26 -0
Index: sparse/ptrlist.c
===================================================================
@@ -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;
+}
+
+
+
+