Crash, apparent memory corruption

Crash, apparent memory corruption

[Pavel Roskin]

Hello!

I was trying to use current sparse from git on the current ndiswrapper.
The system is Fedora 8 x86_64 with all updates.  Just in case, the
kernel is from "wireless-2.6" repository, branch "everything".

When trying to use sparse on ndiswrapper, I found that sparse crashes on
a file called hal.c.  I made a version of the file after preprocessing
and put it here:

http://red-bean.com/proski/sparse/hal.c.bz2

The end of the output looks like this:

hal.c:19756:7: warning: label 'continue' already bound
hal.c:19756:7: warning: label 'break' already bound
hal.c:19756:125: warning: label 'continue' already bound
hal.c:19756:125: warning: label 'break' already bound
Segmentation fault (core dumped)

I guess sparse is already confused about something at this point.  The
full output to stderr is here:

http://red-bean.com/proski/sparse/sparse.stderr

And that's what gdb says (sparse was recompiled without optimization for
that):

Core was generated by `sparse hal.c'.
Program terminated with signal 11, Segmentation fault.
#0  0x000000000041aace in ptr_list_size (head=0x2b7ed86d29d0) at ptrlist.c:26
26                              nr += list->nr;
(gdb) p list
$1 = (struct ptr_list *) 0x5f7265776f6c000a
(gdb) p *list
Cannot access memory at address 0x5f7265776f6c000a
(gdb) where
#0  0x000000000041aace in ptr_list_size (head=0x2b7ed86d29d0) at ptrlist.c:26
#1  0x0000000000418004 in pseudo_list_size (list=0x2b7ed86d29d0) at lib.h:144
#2  0x0000000000417f40 in linearize_compound_statement (ep=0x2b7ed86b5520, stmt=0x2b7ed864e690) at linearize.c:1639
#3  0x000000000041810b in linearize_inlined_call (ep=0x2b7ed86b5520, stmt=0x2b7ed864e690) at linearize.c:1667
#4  0x0000000000418f67 in linearize_statement (ep=0x2b7ed86b5520, stmt=0x2b7ed864e690) at linearize.c:1957
#5  0x0000000000417bbf in linearize_expression (ep=0x2b7ed86b5520, expr=0x2b7ed85b9410) at linearize.c:1546
#6  0x0000000000418abf in linearize_statement (ep=0x2b7ed86b5520, stmt=0x2b7ed84fcdb0) at linearize.c:1868
#7  0x0000000000417ecc in linearize_compound_statement (ep=0x2b7ed86b5520, stmt=0x2b7ed84fcd60) at linearize.c:1629
#8  0x0000000000418f86 in linearize_statement (ep=0x2b7ed86b5520, stmt=0x2b7ed84fcd60) at linearize.c:1958
#9  0x0000000000419722 in linearize_fn (sym=0x2b7ed86073f0, base_type=0x2b7ed8605010) at linearize.c:2126
#10 0x000000000041988c in linearize_symbol (sym=0x2b7ed86073f0) at linearize.c:2195
#11 0x00000000004017cf in check_symbols (list=0x2b7ed85c3310) at sparse.c:266
#12 0x000000000040188f in main (argc=2, argv=0x7fffd3790d88) at sparse.c:284
(gdb)

Using valgrind, I don't see any relevant warnings before the place where
sparse crashes.

Pointer 0x5f7265776f6c000a looks fishy to me.  The initial bytes make
"lower_" if read in ASCII and consider that x86_64 is little endian.

Indeed, it must be coming from "lower_irql" used in the source.  If I
change that name, the pointer changes accordingly.  Moreover, 0x0a is
the symbol length, 10 characters, and it would change if I use a name of
a different length.

Any ideas how to debug it?

-- 
Regards,
Pavel Roskin

Re: Crash, apparent memory corruption

[Pavel Roskin]

Hello!

Here are my results so far.

It's not just the "next" pointer that is corrupted.  The "nr" field in
struct ptr_list is corrupted too.  It becomes -1, which is an invalid
value.  This can be reproduced on both i386 and x86_64 platforms.

The earliest signs of problem I could find are in simplify_one_symbol().
The lower 4 bytes of insn->phi_list->list[0] should be a valid nr (from
0 to 29), but it's 0xffffffff.

I also found the place where -1 comes from.  If I change -1 to -2 in
symbol_pseudo(), the lower 4 bytes of insn->phi_list->list[0] become
0xfffffffe.  It other words, the same area of memory is treated as
struct ptr_list and as pseudo_t.

Here's the patch that demonstrates the problem.

diff --git a/flow.c b/flow.c
index 82fb23a..4946388 100644
--- a/flow.c
+++ b/flow.c
@@ -620,6 +620,7 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 		/* We know that the symbol-pseudo use is the "src" in the instruction */
 		struct instruction *insn = pu->insn;
 
+		fprintf(stderr, "nr = %lx\n", (long int)(insn->phi_list->list[0]));
 		switch (insn->opcode) {
 		case OP_STORE:
 			stores++;
diff --git a/linearize.c b/linearize.c
index 8a68f05..fb03a4b 100644
--- a/linearize.c
+++ b/linearize.c
@@ -761,7 +761,7 @@ static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym)
 	pseudo = sym->pseudo;
 	if (!pseudo) {
 		pseudo = __alloc_pseudo(0);
-		pseudo->nr = -1;
+		pseudo->nr = -2;
 		pseudo->type = PSEUDO_SYM;
 		pseudo->sym = sym;
 		pseudo->ident = sym->ident;


-- 
Regards,
Pavel Roskin

Re: Crash, apparent memory corruption

[Pavel Roskin]

OK, I think I know what's wrong.

The "phi_list" field in "struct instruction" should only be accessed if
"opcode" in the same structure is OP_PHI.  "phi_list" is a part of a
transparent union, and thus could overlap with other data, including
data of the "pseudo_t" type.

linearize_compound_statement() uses "phi_list" unconditionally, but
"opcode" can be OP_INLINED_CALL in some cases.

It's a pure coincidence that pseudo_list_size() avoids crashing in most
cases and returns some number.  That number has to be 1 to enable some
additional logic, which is quite unlikely for invalid data.

I don't know the code enough to fix it properly.  I don't know if it's
OK for "opcode" not to be OP_PHI in linearize_compound_statement().

One approach would be to use assert() to ensure it.  The problem is,
it's triggered on several files in the testsuite.  Here's the patch
anyway:

diff --git a/linearize.c b/linearize.c
index 8a68f05..a907c50 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1636,6 +1636,7 @@ static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct state
 		if (!phi_node)
 			return pseudo;
 
+		assert(phi_node->opcode != OP_PHI);
 		if (pseudo_list_size(phi_node->phi_list)==1) {
 			pseudo = first_pseudo(phi_node->phi_list);
 			assert(pseudo->type == PSEUDO_PHI);

Another approach would be to act like pseudo_list_size() returns a
number other than 1 if opcode is not OP_PHI:

diff --git a/linearize.c b/linearize.c
index 8a68f05..11f3a8b 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1636,7 +1636,8 @@ static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct state
 		if (!phi_node)
 			return pseudo;
 
-		if (pseudo_list_size(phi_node->phi_list)==1) {
+		if (phi_node->opcode == OP_PHI
+		    && pseudo_list_size(phi_node->phi_list) == 1) {
 			pseudo = first_pseudo(phi_node->phi_list);
 			assert(pseudo->type == PSEUDO_PHI);
 			return pseudo->def->src1;

Not only the testsuite passes, but I can also check the kernel and
ndiswrapper without sparse crashes.

But I don't know whether the patch is hiding the problem instead of
fixing it.  And we may want to have an additional tag in memory to make
sure that the lists are of the correct type.

-- 
Regards,
Pavel Roskin