dissect.c

I completely forgot to re-send this patch, sorry. Nothing was changed, except now ->r_symdef() is called for NS_STRUCT symbols too, to report a struct/union definition.

 Makefile       |    9 
 dissect.h      |   40 +++
 dissect.c      |  574 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 test-dissect.c |   95 +++++++++
 4 files changed, 716 insertions(+), 2 deletions(-)

This patch adds dissect.{h,c} files to the sparse distribution. From dissect.h:

	struct reporter
	{
		void (*r_symdef)(struct symbol*);

		void (*r_symbol)(unsigned mode, struct position*, struct symbol*);
		void (*r_member)(unsigned mode, struct position*, struct symbol*, struct symbol*);
	};

	extern void dissect(struct symbol_list*, struct reporter*);

dissect() walks the output of the sparse_file() and calls reporter's callbacks.

->r_symdef() is called when the symbol (variable or function) is defined.

->r_symbol() - when the symbol is used in any way. The 'mode' parameter denotes how this symbol was used. It is a bitmask of possible flags:

	FLAG:		Code example:

	U_R_VAL		return VAR;
	U_W_VAL		VAR = 0;

	U_R_PTR		return *VAR;
	U_W_PTR		*VAR = 0;

	U_R_AOF		const void *... = &VAR;
	U_W_AOF		memset(&VAR, ...);

->r_member() tracks the use of members of structures in the same way.

This patch also adds test-dissect.c, a simple and stupid example. It prints the 'mode' parameter in a human readable format along with the storage info, variable's name (or struct_name.member_name), and it's type.

The 'mode' is dumped as a 3-letter string. The first letter denotes AOF part, 2-nd - VAL, 3-rd - PTR.

	0			-> '-'
	U_R_xxx			-> 'r'
	U_W_xxx			-> 'w'
	U_R_xxx | U_W_xxx	-> 'm'

Example:

	$ cat -n T.c
	     1  int var;
	     2
	     3  static void func(void)
	     4  {
	     5          int *ptr;
	     6
	     7          ptr = &var;
	     8          *ptr = var;
	     9
	    10          var = *++ptr;
	    11  }

	$ ./test-dissect T.c

FILE: T.c

1:5 g def var int
3:13 s def func void ( )( ... )
5:6 l def ptr int *
7:2 l -w- ptr int *
7:9 g m-- var int
8:3 l --w ptr int *
8:9 g -r- var int
10:2 g -w- var int
10:11 l -mr ptr int *

Note that '*ptr' does not add U_R_VAL flag, this is a feature, not a bug, even if technically wrong.

dissect() does not check the code for correctness, for example:

	0 = X = Y;

gives this output:

   5:6   g -w-  X                                bad type
   5:10  g -r-  Y                                bad type

Again, X has no U_R_VAL, notabug.

Members of structures usage:

	task_t *tsk;
	tsk->parent->real_parent->pid++;

output:

   7:2   l --r  tsk                              struct task_struct [usertype] *
   7:5   g --r  task_struct.parent               struct task_struct *
   7:13  g --m  task_struct.real_parent          struct task_struct *
   7:26  g -m-  task_struct.pid                  int

dissect() tries to de-anonymize unnamed structures/unions:

     1  struct T {
     2          struct {
     3                  int x, y;
     4          } m;
     5  } t = {
     6          { undeclared }
     7  };

output:

   5:3   g def  t                                struct T
   5:3   g -w-  t                                struct T
   6:2   s -w-  T.m                              struct T:m
   6:4   s -w-  T:m.x                            int
   6:4   g -r-  undeclared                       bad type

When entire struct is overwritten, ->r_member() is called with mem == NULL, this reported as struct_name.*, example:

	*new_vma = *vma;

output:

2028:5   l --w  new_vma                          struct vm_area_struct *
2028:13  g -w-  vm_area_struct.*                 struct vm_area_struct
2028:13  g -w-  pgprot_t.*                       struct pgprot_t
2028:13  g -w-  rb_node.*                        struct rb_node
2028:13  g -w-  vm_area_struct:shared.*          union vm_area_struct:shared
2028:13  g -w-  vm_area_struct:shared:vm_set.*   struct vm_area_struct:shared:vm_set
2028:13  g -w-  list_head.*                      struct list_head
2028:13  g -w-  raw_prio_tree_node.*             struct raw_prio_tree_node
2028:13  g -w-  list_head.*                      struct list_head
2028:16  l --r  vma                              struct vm_area_struct *

Function calls use U_R_PTR bit:

     5          func();
     6          pf = func;
     7          pf();

   5:2   g --r  func                             void (  )( ... )
   6:2   l -w-  pf                               void ( * )( ... )
   6:7   g r--  func                             void (  )( ... )
   7:2   l --r  pf                               void ( * )( ... )

BUGS:

1. dissect() confuses array-in-container with a pointer:

     3          struct T { int ary[]; } t;
     4
     5          t.ary[0] = 0;

output:

   5:2   l -r-  t     /* BUG, should be -w- */   struct T
   5:3   s -w-  T.ary                            int [0]

2. It can't detect the case when the address is taken only for writing,
eg: *(&i + 1) = 0, so U_W_AOF always implies U_R_AOF.

3. It does not support "flat" initializers without braces:

     3          struct O {
     4                  struct I {
     5                          int x, y;
     6                  } a, b;
     7          };
     8
     9          struct O o1 = { 1, 2, 3 };

buggy output:

   9:11  l -w-  o1                               struct O
   9:18  s -w-  O.a                              struct I
   9:21  s -w-  O.b                              struct I
   9:24  s -w-  O.?                              bad type

This is ok:

    11          struct O o2 = { { 1 }, .b = { .y = 0 } };

  11:11  l -w-  o2                               struct O
  11:18  s -w-  O.a                              struct I
  11:20  s -w-  I.x                              int
  11:30  s -w-  O.b                              struct I
  11:37  s -w-  I.y                              int

4. The implementation is far from perfect. It was really done in "add some code + printf and see what happens" manner, without studying the sources first. However I beleive it may be useful for others, that is why I am posting it.

@@ -21,7 +21,7 @@ CFLAGS += -DDEBUG
 
 PREFIX=$(HOME)
 BINDIR=$(PREFIX)/bin
-PROGRAMS=test-lexing test-parsing obfuscate check compile test-linearize example test-unssa
+PROGRAMS=test-lexing test-parsing obfuscate check compile test-linearize example test-unssa test-dissect
 
 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 \

@@ -30,7 +30,7 @@ LIB_H=    token.h parse.h lib.h symbol.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
+	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
 
 LIB_FILE= libsparse.a
 SLIB_FILE= libsparse.so

@@ -83,6 +83,9 @@ example: example.o $(LIBS)
 test-unssa: test-unssa.o $(LIBS)
 	$(CC) $(LDFLAGS) -o $@ $< $(LIBS)
 
+test-dissect: test-dissect.o $(LIBS)
+	$(CC) $(LDFLAGS) -o $@ $< $(LIBS)
+
 $(LIB_FILE): $(LIB_OBJS)
 	$(AR) rcs $@ $(LIB_OBJS)
 

@@ -111,6 +114,7 @@ target.o: $(LIB_H)
 test-lexing.o: $(LIB_H)
 test-parsing.o: $(LIB_H)
 test-linearize.o: $(LIB_H)
+test-dissect.o: $(LIB_H) dissect.h
 compile.o: $(LIB_H) compile.h
 compile-i386.o: $(LIB_H) compile.h
 tokenize.o: $(LIB_H)

@@ -118,6 +122,7 @@ check.o: $(LIB_H)
 obfuscate.o: $(LIB_H)
 example.o: $(LIB_H)
 storage.o: $(LIB_H) storage.h
+dissect.o: $(LIB_H) dissect.h
 
 compat-linux.o: compat/strtold.c compat/mmap-blob.c \
 	$(LIB_H)

@@ -0,0 +1,40 @@
+#ifndef	DISSECT_H
+#define	DISSECT_H
+
+#include <stdio.h>
+#include "parse.h"
+#include "expression.h"
+
+#define	U_SHIFT		8
+
+#define	U_R_AOF		0x01
+#define	U_W_AOF		0x02
+
+#define	U_R_VAL		0x04
+#define	U_W_VAL		0x08
+
+#define	U_R_PTR		(U_R_VAL << U_SHIFT)
+#define	U_W_PTR		(U_W_VAL << U_SHIFT)
+
+struct reporter
+{
+	void (*r_symdef)(struct symbol*);
+
+	void (*r_symbol)(unsigned, struct position*, struct symbol*);
+	void (*r_member)(unsigned, struct position*, struct symbol*, struct symbol*);
+};
+
+extern void dissect(struct symbol_list*, struct reporter*);
+
+#define	MK_IDENT(s)	({				\
+	static struct {					\
+		struct ident ident;			\
+		char __[sizeof(s)];			\
+	} ident = {{					\
+		.len  = sizeof(s)-1,			\
+		.name = s,				\
+	}};						\
+	&ident.ident;					\
+})
+
+#endif