Adding the NULL pointer checker.

PATCH In review Christopher Li 3 participants 5 messages Jan 17, 2007 – Jan 29, 2007

Subsystems (2)

Kbuild Sparse checker

lore

Share & tools

lore

Christopher Li

author maintainer

2007-01-17 03:02 UTC #0 lore raw

PATCH 1/1 Adding the NULL pointer checker.

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<[email protected]>

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 +108 -0

108 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 +297 -0

297 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;
+}
+
+
+
+

Christopher Li

author maintainer

2007-01-17 03:04 UTC #1 lore raw

Oops, this should be [PATCH 6] instead.

Chris

Quoted 14 lines · 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<[email protected]>

Josh Triplett

2007-01-27 08:21 UTC #2 lore raw

In reply to Christopher Li

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

Quoted 3 lines · Christopher Li

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.

Quoted 2 lines

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.

checker.h line 5

Quoted 8 lines

checker.h +5 -0

@@ -0,0 +1,108 @@
+#ifndef _CHECKER_H_
+#define _CHECKER_H_
+
+struct blob {
+	int len;

size_t len, please.

Quoted 2 lines

checker.h +2 -0

+	unsigned char data[0];
+};

[...]

expand.c line 33

Quoted 10 lines

expand.c +2 -2

@@ -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.

Quoted 3 lines

sparse.c +0 -0
 };

[...]

Quoted 19 lines

static void check_call_instruction(struct instruction *insn) {

sparse.c +2 -6

 	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;

sparse.c struct checkfn { · line 208

Quoted 10 lines

sparse.c +3 -6

-	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.

sparse.c enum opcode { · line 217

Quoted 6 lines

sparse.c +1 -0

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

Hmmm...

Quoted 2 lines

check-interrupt.c +0 -0

[...]

check-interrupt.c line 29

Quoted 5 lines

check-interrupt.c +5 -0

+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?

Quoted 12 lines

check-interrupt.c +12 -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);

check-interrupt.c line 141

Quoted 10 lines

check-interrupt.c +10 -0

+				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.

[...]

check-interrupt.c

Quoted 5 lines

check-interrupt.c +5 -0

+enum {
+	OP_DEF_PTR = OP_LAST,
+	OP_USE_PTR,
+	OP_FREE_PTR
+};

Same problem as above.

check-interrupt.c

Quoted 5 lines

check-interrupt.c +5 -0

+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/.

check-interrupt.c

Quoted 3 lines

check-interrupt.c +3 -0

+	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.

check-interrupt.c

Quoted 5 lines

check-interrupt.c +5 -0

+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.

check-interrupt.c

Quoted 5 lines

check-interrupt.c +5 -0

+	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.

Quoted 15 lines

check-interrupt.c +15 -0

+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",

check-interrupt.c

Quoted 10 lines

check-interrupt.c +10 -0

+		"__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.

check-interrupt.c

Quoted 4 lines

check-interrupt.c +4 -0

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

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

- Josh Triplett

Chris Li

author maintainer

2007-01-29 22:31 UTC #3 lore raw

Quoted 8 lines

expand.c 2007-01-16 11:13:28.000000000 -0800
Quoted 6 lines
expand.c 2007-01-16 11:13:28.000000000 -0800 renamed from expand.c 2007-01-16 11:13:18.000000000 -0800 +2 -2
-#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.

Quoted 2 lines

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.

Quoted 6 lines

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[])

Quoted 8 lines

{
        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);

Quoted 5 lines

Quoted 3 lines
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.

Quoted 11 lines

checker.h 2007-01-16 11:57:29.000000000 -0800 line 5
Quoted 9 lines
checker.h 2007-01-16 11:57:29.000000000 -0800 renamed from checker.h 2007-01-16 11:13:28.000000000 -0800 +5 -0
@@ -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.

Quoted 8 lines

Quoted 3 lines
checker.h 2007-01-16 11:57:29.000000000 -0800 renamed from checker.h 2007-01-16 11:13:28.000000000 -0800 +2 -0
+     unsigned char data[0];
+};
[...]
Quoted 1 line
--- 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.

Quoted 13 lines

checker.h 2007-01-16 11:57:29.000000000 -0800 enum opcode { · line 217
Quoted 7 lines
checker.h 2007-01-16 11:57:29.000000000 -0800 renamed from checker.h 2007-01-16 11:13:28.000000000 -0800 +1 -0
@@ -211,14 +213,19 @@ enum opcode {
 
      /* Needed to translate SSA back to normal form */
      OP_COPY,
+     OP_LAST,
 };
Hmmm...
Quoted 2 lines
check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 renamed from check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 +0 -0
[...]

Quoted 8 lines

check-interrupt.c 2007-01-16 11:13:28.000000000 -0800
Quoted 5 lines
check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 renamed from check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 +5 -0
+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.

Quoted 4 lines

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.

Quoted 27 lines

Quoted 13 lines

check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 renamed from check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 +12 -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);

check-interrupt.c 2007-01-16 11:13:28.000000000 -0800

Quoted 10 lines

check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 renamed from check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 +10 -0

+                             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.

Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 7 lines

check-interrupt.c 2007-01-16 11:13:28.000000000 -0800
Quoted 5 lines
check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 renamed from check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 +5 -0
+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.

Quoted 2 lines

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.

Quoted 8 lines

check-interrupt.c 2007-01-16 11:13:28.000000000 -0800
Quoted 5 lines
check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 renamed from check-interrupt.c 2007-01-16 11:13:28.000000000 -0800 +4 -0
+     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

Linus Torvalds

2007-01-29 22:48 UTC #4 lore raw

Quoted 7 lines · Chris Li

Quoted 7 lines
expand.c 2007-01-16 11:13:28.000000000 -0800
Quoted 3 lines
expand.c 2007-01-16 11:13:28.000000000 -0800 renamed from expand.c 2007-01-16 11:13:18.000000000 -0800 +0 -1
-#define SELECT_COST 20               /* Cut-off for turning a conditional
into a select */
expand.c 2007-01-16 11:13:28.000000000 -0800
Quoted 2 lines
expand.c 2007-01-16 11:13:28.000000000 -0800 renamed from expand.c 2007-01-16 11:13:18.000000000 -0800 +1 -1
-#define BRANCH_COST 10               /* Cost of a conditional branch */
+#define SELECT_COST 0                /* Cut-off for turning a conditional
into a select */

Quoted 6 lines

Quoted 3 lines
Quoted 1 line
+#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