Stale expression reference causing use-after-free

Stale expression reference causing use-after-free

[Arnaud Lacombe]

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

Hi,

I've been experiencing a use-after-free with the current kconfig (from
for-next, but I believe mainline is affected too), related to the
introduction of commit 246cf9c26bf11f2bffbecea6e5bd222eee7b1df8. The
symptoms with the attached test case and patch to highlight the
problem is the following:

% scripts/kconfig/mconf Kconfig.testcase
[...]
Invalid expr 0xbb9124a0 at scripts/kconfig/menu.c:295 in
menu_finalize(): 41414141
zsh: abort (core dumped)  scripts/kconfig/mconf Kconfig.testcase

The backtrace is not really surprising:

#2  0xbbb9fbd6 in abort () from /usr/lib/libc.so.12
#3  0x0804f23a in menu_finalize (parent=0xbb911e20) at
scripts/kconfig/menu.c:295
#4  0x0804eb6d in menu_finalize (parent=0xbb911df0) at
scripts/kconfig/menu.c:292
#5  0x0804f166 in menu_finalize (parent=0xbb911d60) at
scripts/kconfig/menu.c:320
#6  0x0804eb6d in menu_finalize (parent=0xbb911c10) at
scripts/kconfig/menu.c:292
#7  0x0804eb6d in menu_finalize (parent=0x8069ea0) at scripts/kconfig/menu.c:292
#8  0x080535d7 in conf_parse (name=0x804aa61 "Ç\004$") at
scripts/kconfig/zconf.tab.c:2242
#9  0x0804aa61 in main (ac=Cannot access memory at address 0x0

(gdb) frame 3
#3  0x0804f23a in menu_finalize (parent=0xbb911e20) at
scripts/kconfig/menu.c:295
295                     EXPR_CHECK(parent->dir_dep);

So far, I tracked this issue down to the faulty expression being freed
by expr_eliminate_dups1() in the previous iteration of
menu_initialize(), on the following line

basedep = expr_eliminate_dups(basedep);

The testcase is a stripped down Kconfig from the tree.

 - Arnaud

[-- Attachment #2: Kconfig.testcase --]
[-- Type: application/octet-stream, Size: 29 bytes --]

source "Kconfig.testcase.l1"

[-- Attachment #3: Kconfig.testcase.l1 --]
[-- Type: application/octet-stream, Size: 3172 bytes --]

config DUMMY_BOOL_0
	bool

config DUMMY_BOOL_1
	bool

config DUMMY_BOOL_2
	bool

config DUMMY_BOOL_3
	bool
	default y

config DUMMY_BOOL_4
	bool
	default (DUMMY_COND_5 || DUMMY_COND_6)

config DUMMY_STRING_0
	string
	default "string0" if DUMMY_COND_7
	default "string1" if DUMMY_COND_8

config DUMMY_BOOL_5 # maybe unneeded
	bool
	default y

config DUMMY_BOOL_6
	bool
	default y

config DUMMY_BOOL_7
	bool
	default y
	select DUMMY_SELECT_0 if DUMMY_COND_0
	select DUMMY_SELECT_1
	select DUMMY_SELECT_2
	select DUMMY_SELECT_3
	select DUMMY_SELECT_4

config DUMMY_BOOL_8
	bool
	default y
	depends on DUMMY_COND_9 || (DUMMY_COND_10 && DUMMY_COND_11)

config DUMMY_BOOL_9
	bool
	default y
	select DUMMY_SELECT_5
	select DUMMY_SELECT_6
	select DUMMY_SELECT_7 if (!DUMMY_COND_1 || !DUMMY_COND_2)
	select DUMMY_SELECT_8
	select DUMMY_SELECT_9

config DUMMY_BOOL_10
	bool
	default y
	select DUMMY_SELECT_10
	select DUMMY_SELECT_11
	select DUMMY_SELECT_12
	select DUMMY_SELECT_13
	select DUMMY_SELECT_14

config DUMMY_BOOL_11
	bool
	default y
	select DUMMY_SELECT_15
	select DUMMY_SELECT_16
	select DUMMY_SELECT_17
	select DUMMY_SELECT_18
	select DUMMY_SELECT_19

config DUMMY_BOOL_12
	bool
	default y
	select DUMMY_SELECT_20 if DUMMY_COND_3
	select DUMMY_SELECT_21
	select DUMMY_SELECT_22
	select DUMMY_SELECT_23
	select DUMMY_SELECT_24

config DUMMY_BOOL_13
	bool
	default (DUMMY_COND_12 || DUMMY_COND_13 || DUMMY_COND_14)
	select DUMMY_SELECT_25
	select DUMMY_SELECT_26 if DUMMY_COND_4
	select DUMMY_SELECT_27
	select DUMMY_SELECT_28
	select DUMMY_SELECT_29

config DUMMY_BOOL_14
	bool
	default y
	depends on DUMMY_COND_15
	select DUMMY_SELECT_30
	select DUMMY_SELECT_31
	select DUMMY_SELECT_32
	select DUMMY_SELECT_33
	select DUMMY_SELECT_34 if DUMMY_COND_16

config DUMMY_BOOL_16
	bool
	default y

config DUMMY_BOOL_17
	bool
	default y

config DUMMY_BOOL_18
	bool
	default y

config DUMMY_BOOL_19
	bool
	default y

config DUMMY_BOOL_20
	bool
	default y

config DUMMY_BOOL_21
	bool
	default y

config DUMMY_BOOL_22
	bool
	default y

config DUMMY_BOOL_23
	bool
	default y

config DUMMY_BOOL_24
	bool
	default y

config DUMMY_BOOL_30
	bool
	default y

config DUMMY_BOOL_25
	bool
	default y

config DUMMY_BOOL_26
	bool
	default y

config DUMMY_BOOL_27
	bool
	default y

config DUMMY_BOOL_28
	bool
	default y

config DUMMY_BOOL_29
	bool
	default y

config DUMMY_BOOL_30
	bool
	default y
	depends on DUMMY_COND_17 && DUMMY_COND_18 && DUMMY_COND_19

config DUMMY_STRING_1
	string
	option env="ENV0"

config DUMMY_STRING_2
	string
	option env="ENV1"

config DUMMY_STRING_3
	string
	depends on !UML
	option defconfig_list
	default "string2"
	default "string3"
	default "string4"
	default "_string5"
	default "string6"

menu "dummy menu 0"

config DUMMY_BOOL_31
	bool "prompt0"

config DUMMY_BOOL_32
	bool

menuconfig DUMMY_BOOL_33
	bool "prompt1"
	depends on DUMMY_COND_20

if DUMMY_BOOL_33

config DUMMY_BOOL_34
	bool "prompt2"
	depends on DUMMY_BOOL_33

config DUMMY_BOOL_35
	bool "prompt3"
	depends on DUMMY_COND_21

config DUMMY_BOOL_36
	bool "prompt4"
	depends on DUMMY_COND_22 && DUMMY_COND_23

menuconfig DUMMY_BOOL_37
	bool "prompt5"
	depends on DUMMY_COND_24

endif

endmenu


[-- Attachment #4: instrumentation.diff --]
[-- Type: text/x-patch, Size: 6288 bytes --]

diff --git a/Kconfig.testcase b/Kconfig.testcase
new file mode 100644
index 0000000..cb663e9
--- /dev/null
+++ b/Kconfig.testcase
@@ -0,0 +1 @@
+source "Kconfig.testcase.l1"
diff --git a/Kconfig.testcase.l1 b/Kconfig.testcase.l1
new file mode 100644
index 0000000..79ec19e
--- /dev/null
+++ b/Kconfig.testcase.l1
@@ -0,0 +1,216 @@
+config DUMMY_BOOL_0
+	bool
+
+config DUMMY_BOOL_1
+	bool
+
+config DUMMY_BOOL_2
+	bool
+
+config DUMMY_BOOL_3
+	bool
+	default y
+
+config DUMMY_BOOL_4
+	bool
+	default (DUMMY_COND_5 || DUMMY_COND_6)
+
+config DUMMY_STRING_0
+	string
+	default "string0" if DUMMY_COND_7
+	default "string1" if DUMMY_COND_8
+
+config DUMMY_BOOL_5 # maybe unneeded
+	bool
+	default y
+
+config DUMMY_BOOL_6
+	bool
+	default y
+
+config DUMMY_BOOL_7
+	bool
+	default y
+	select DUMMY_SELECT_0 if DUMMY_COND_0
+	select DUMMY_SELECT_1
+	select DUMMY_SELECT_2
+	select DUMMY_SELECT_3
+	select DUMMY_SELECT_4
+
+config DUMMY_BOOL_8
+	bool
+	default y
+	depends on DUMMY_COND_9 || (DUMMY_COND_10 && DUMMY_COND_11)
+
+config DUMMY_BOOL_9
+	bool
+	default y
+	select DUMMY_SELECT_5
+	select DUMMY_SELECT_6
+	select DUMMY_SELECT_7 if (!DUMMY_COND_1 || !DUMMY_COND_2)
+	select DUMMY_SELECT_8
+	select DUMMY_SELECT_9
+
+config DUMMY_BOOL_10
+	bool
+	default y
+	select DUMMY_SELECT_10
+	select DUMMY_SELECT_11
+	select DUMMY_SELECT_12
+	select DUMMY_SELECT_13
+	select DUMMY_SELECT_14
+
+config DUMMY_BOOL_11
+	bool
+	default y
+	select DUMMY_SELECT_15
+	select DUMMY_SELECT_16
+	select DUMMY_SELECT_17
+	select DUMMY_SELECT_18
+	select DUMMY_SELECT_19
+
+config DUMMY_BOOL_12
+	bool
+	default y
+	select DUMMY_SELECT_20 if DUMMY_COND_3
+	select DUMMY_SELECT_21
+	select DUMMY_SELECT_22
+	select DUMMY_SELECT_23
+	select DUMMY_SELECT_24
+
+config DUMMY_BOOL_13
+	bool
+	default (DUMMY_COND_12 || DUMMY_COND_13 || DUMMY_COND_14)
+	select DUMMY_SELECT_25
+	select DUMMY_SELECT_26 if DUMMY_COND_4
+	select DUMMY_SELECT_27
+	select DUMMY_SELECT_28
+	select DUMMY_SELECT_29
+
+config DUMMY_BOOL_14
+	bool
+	default y
+	depends on DUMMY_COND_15
+	select DUMMY_SELECT_30
+	select DUMMY_SELECT_31
+	select DUMMY_SELECT_32
+	select DUMMY_SELECT_33
+	select DUMMY_SELECT_34 if DUMMY_COND_16
+
+config DUMMY_BOOL_16
+	bool
+	default y
+
+config DUMMY_BOOL_17
+	bool
+	default y
+
+config DUMMY_BOOL_18
+	bool
+	default y
+
+config DUMMY_BOOL_19
+	bool
+	default y
+
+config DUMMY_BOOL_20
+	bool
+	default y
+
+config DUMMY_BOOL_21
+	bool
+	default y
+
+config DUMMY_BOOL_22
+	bool
+	default y
+
+config DUMMY_BOOL_23
+	bool
+	default y
+
+config DUMMY_BOOL_24
+	bool
+	default y
+
+config DUMMY_BOOL_30
+	bool
+	default y
+
+config DUMMY_BOOL_25
+	bool
+	default y
+
+config DUMMY_BOOL_26
+	bool
+	default y
+
+config DUMMY_BOOL_27
+	bool
+	default y
+
+config DUMMY_BOOL_28
+	bool
+	default y
+
+config DUMMY_BOOL_29
+	bool
+	default y
+
+config DUMMY_BOOL_30
+	bool
+	default y
+	depends on DUMMY_COND_17 && DUMMY_COND_18 && DUMMY_COND_19
+
+config DUMMY_STRING_1
+	string
+	option env="ENV0"
+
+config DUMMY_STRING_2
+	string
+	option env="ENV1"
+
+config DUMMY_STRING_3
+	string
+	depends on !UML
+	option defconfig_list
+	default "string2"
+	default "string3"
+	default "string4"
+	default "_string5"
+	default "string6"
+
+menu "dummy menu 0"
+
+config DUMMY_BOOL_31
+	bool "prompt0"
+
+config DUMMY_BOOL_32
+	bool
+
+menuconfig DUMMY_BOOL_33
+	bool "prompt1"
+	depends on DUMMY_COND_20
+
+if DUMMY_BOOL_33
+
+config DUMMY_BOOL_34
+	bool "prompt2"
+	depends on DUMMY_BOOL_33
+
+config DUMMY_BOOL_35
+	bool "prompt3"
+	depends on DUMMY_COND_21
+
+config DUMMY_BOOL_36
+	bool "prompt4"
+	depends on DUMMY_COND_22 && DUMMY_COND_23
+
+menuconfig DUMMY_BOOL_37
+	bool "prompt5"
+	depends on DUMMY_COND_24
+
+endif
+
+endmenu
+
diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c
index 330e7c0..65f7ab3 100644
--- a/scripts/kconfig/expr.c
+++ b/scripts/kconfig/expr.c
@@ -71,6 +71,8 @@ struct expr *expr_copy(struct expr *org)
 	if (!org)
 		return NULL;
 
+	EXPR_CHECK(org);
+
 	e = malloc(sizeof(*org));
 	memcpy(e, org, sizeof(*org));
 	switch (org->type) {
@@ -101,11 +103,13 @@ struct expr *expr_copy(struct expr *org)
 	return e;
 }
 
-void expr_free(struct expr *e)
+void _expr_free(struct expr *e)
 {
 	if (!e)
 		return;
 
+	EXPR_CHECK(e);
+
 	switch (e->type) {
 	case E_SYMBOL:
 		break;
@@ -124,6 +128,9 @@ void expr_free(struct expr *e)
 		printf("how to free type %d?\n", e->type);
 		break;
 	}
+
+	memset(e, 'A', sizeof(e));
+
 	free(e);
 }
 
diff --git a/scripts/kconfig/expr.h b/scripts/kconfig/expr.h
index 6ee2e4f..0adc104 100644
--- a/scripts/kconfig/expr.h
+++ b/scripts/kconfig/expr.h
@@ -48,6 +48,26 @@ struct expr {
 #define EXPR_AND(dep1, dep2)	(((dep1)<(dep2))?(dep1):(dep2))
 #define EXPR_NOT(dep)		(2-(dep))
 
+#if 1
+#define expr_free(e)							\
+({									\
+	fprintf(stderr, "%s: %p:%d\n", __func__, e, __LINE__);		\
+	_expr_free(e);							\
+	e = NULL;							\
+})
+#else
+#define expr_free(e)	_expr_free(e);
+#endif
+
+#define EXPR_CHECK(e)							\
+({									\
+	if ((e) != NULL && ((e)->type < E_NONE || (e)->type > E_RANGE)) { \
+		fprintf(stderr, "Invalid expr %p at %s:%d in %s(): %x\n", \
+		    e, __FILE__, __LINE__, __func__, (e)->type);	\
+		abort();						\
+	}								\
+})
+
 #define expr_list_for_each_sym(l, e, s) \
 	for (e = (l); e && (s = e->right.sym); e = e->left.expr)
 
@@ -193,7 +213,7 @@ struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symb
 struct expr *expr_alloc_and(struct expr *e1, struct expr *e2);
 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2);
 struct expr *expr_copy(struct expr *org);
-void expr_free(struct expr *e);
+void _expr_free(struct expr *e);
 int expr_eq(struct expr *e1, struct expr *e2);
 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2);
 tristate expr_calc_value(struct expr *e);
diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
index 4fb5902..3563239 100644
--- a/scripts/kconfig/menu.c
+++ b/scripts/kconfig/menu.c
@@ -292,6 +292,7 @@ void menu_finalize(struct menu *parent)
 			menu_finalize(menu);
 	} else if (sym) {
 		/* ignore inherited dependencies for dir_dep */
+		EXPR_CHECK(parent->dir_dep);
 		sym->dir_dep.expr = expr_transform(expr_copy(parent->dir_dep));
 		sym->dir_dep.expr = expr_eliminate_dups(sym->dir_dep.expr);
 

Re: Stale expression reference causing use-after-free

[Arnaud Lacombe]

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

Hi,

It would seem that this issue is responsible for the crash I've seen
randomly happening with gconf (2.6.36-rc6, before my generalization's
branch). So far, I've traced it to the following line in
menu_finalize():

sym->dir_dep.expr = expr_transform(expr_copy(parent->dir_dep));

The crash happen in expr_copy(). expr_transform() is never being
called. The trace is the following:

Program received signal SIGSEGV, Segmentation fault.
0xbb1f085c in ?? () from /usr/lib/libc.so.12
(gdb) bt
#0  0xbb1f085c in ?? () from /usr/lib/libc.so.12
#1  0xbb1f0e4b in malloc () from /usr/lib/libc.so.12
#2  0x0805277f in expr_copy (org=0xba790fd0) at scripts/kconfig/expr.c:79
#3  0x080527e9 in expr_copy (org=0xba790fd0) at scripts/kconfig/expr.c:86
#4  0x00000001 in ?? ()
#5  0x00000000 in ?? ()

however, with the small patch attached, we get a bit more information:

(gdb) print expr_copy_nest
$1 = 43391

After reducing the stack size from 2048k (default) to 1024k:

(gdb) print expr_copy_nest
$1 = 21545

and bumping it to 4096k:

(gdb) print expr_copy_nest
$1 = 87081

so we're dying from stack exhaustion, because expr_copy() is given a
really nasty symbol:

(gdb) print org
$5 = (struct expr *) 0xba790fd0
(gdb) print *org
$6 = {type = E_NOT, left = {expr = 0xba790fd0, sym = 0xba790fd0},
right = {expr = 0x0, sym = 0x0}}

Reverting 246cf9c26bf11f2bffbecea6e5bd222eee7b1df8 fixes the crash.

 - Arnaud


On Sun, Sep 19, 2010 at 12:56 AM, Arnaud Lacombe <lacombar@gmail.com> wrote:
> Hi,
>
> I've been experiencing a use-after-free with the current kconfig (from
> for-next, but I believe mainline is affected too), related to the
> introduction of commit 246cf9c26bf11f2bffbecea6e5bd222eee7b1df8. The
> symptoms with the attached test case and patch to highlight the
> problem is the following:
>
> % scripts/kconfig/mconf Kconfig.testcase
> [...]
> Invalid expr 0xbb9124a0 at scripts/kconfig/menu.c:295 in
> menu_finalize(): 41414141
> zsh: abort (core dumped)  scripts/kconfig/mconf Kconfig.testcase
>
> The backtrace is not really surprising:
>
> #2  0xbbb9fbd6 in abort () from /usr/lib/libc.so.12
> #3  0x0804f23a in menu_finalize (parent=0xbb911e20) at
> scripts/kconfig/menu.c:295
> #4  0x0804eb6d in menu_finalize (parent=0xbb911df0) at
> scripts/kconfig/menu.c:292
> #5  0x0804f166 in menu_finalize (parent=0xbb911d60) at
> scripts/kconfig/menu.c:320
> #6  0x0804eb6d in menu_finalize (parent=0xbb911c10) at
> scripts/kconfig/menu.c:292
> #7  0x0804eb6d in menu_finalize (parent=0x8069ea0) at scripts/kconfig/menu.c:292
> #8  0x080535d7 in conf_parse (name=0x804aa61 "Ç\004$") at
> scripts/kconfig/zconf.tab.c:2242
> #9  0x0804aa61 in main (ac=Cannot access memory at address 0x0
>
> (gdb) frame 3
> #3  0x0804f23a in menu_finalize (parent=0xbb911e20) at
> scripts/kconfig/menu.c:295
> 295                     EXPR_CHECK(parent->dir_dep);
>
> So far, I tracked this issue down to the faulty expression being freed
> by expr_eliminate_dups1() in the previous iteration of
> menu_initialize(), on the following line
>
> basedep = expr_eliminate_dups(basedep);
>
> The testcase is a stripped down Kconfig from the tree.
>
>  - Arnaud
>

[-- Attachment #2: expr.c.diff --]
[-- Type: text/x-patch, Size: 662 bytes --]

diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c
index ccd6563..e2b7f01 100644
--- a/scripts/kconfig/expr.c
+++ b/scripts/kconfig/expr.c
@@ -63,12 +59,18 @@ struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
 	return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
 }
 
+int expr_copy_nest = 0;
+
 struct expr *expr_copy(struct expr *org)
 {
 	struct expr *e;
 
-	if (!org)
-		return NULL;
+	expr_copy_nest++;
+
+	if (!org) {
+		e = NULL;
+		goto bail_out;
+	}
 
 	e = malloc(sizeof(*org));
 	memcpy(e, org, sizeof(*org));
@@ -97,6 +99,9 @@ struct expr *expr_copy(struct expr *org)
 		break;
 	}
 
+bail_out:
+	expr_copy_nest--;
+
 	return e;
 }
 

Re: Stale expression reference causing use-after-free

[Catalin Marinas]

Hi Arnaud,

On Sun, 2010-09-19 at 22:54 -0400, Arnaud Lacombe wrote:
> It would seem that this issue is responsible for the crash I've seen
> randomly happening with gconf (2.6.36-rc6, before my generalization's
> branch). So far, I've traced it to the following line in
> menu_finalize():
> 
> sym->dir_dep.expr = expr_transform(expr_copy(parent->dir_dep));
> 
> The crash happen in expr_copy(). expr_transform() is never being
> called. The trace is the following:
> 
> Program received signal SIGSEGV, Segmentation fault.
[...]
> so we're dying from stack exhaustion, because expr_copy() is given a
> really nasty symbol:
[...]
> Reverting 246cf9c26bf11f2bffbecea6e5bd222eee7b1df8 fixes the crash.

Thanks for investigating this. The expr_copy() is a recursive function
and it could indeed run out of stack.

I wonder if we really need the expr_copy() here. It looks to me like
expr_transform() already does some memory allocations:


kbuild: Avoid additional copy of the 'depends' expression

From: Catalin Marinas <catalin.marinas@arm.com>

Commit 246cf9c26b introduced the tracking of direct dependency to
provide additional warning when they are not met. With some complex
dependencies, the expr_copy() function called on such expressions may
cause stack exhaustion. The patch removes the superfluous expr_copy()
call since expr_transform handles symbol duplication already.

Signed-off-by: Catalin Marinas <catalin.marinas@arm.com>
Reported-by: Arnaud Lacombe <lacombar@gmail.com>
---
 scripts/kconfig/menu.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
index 4fb5902..7298806 100644
--- a/scripts/kconfig/menu.c
+++ b/scripts/kconfig/menu.c
@@ -292,7 +292,7 @@ void menu_finalize(struct menu *parent)
 			menu_finalize(menu);
 	} else if (sym) {
 		/* ignore inherited dependencies for dir_dep */
-		sym->dir_dep.expr = expr_transform(expr_copy(parent->dir_dep));
+		sym->dir_dep.expr = expr_transform(parent->dir_dep);
 		sym->dir_dep.expr = expr_eliminate_dups(sym->dir_dep.expr);
 
 		basedep = parent->prompt ? parent->prompt->visible.expr : NULL;


-- 
Catalin

Re: Stale expression reference causing use-after-free

[Arnaud Lacombe]

Hi Catalin,

On Tue, Sep 21, 2010 at 8:32 AM, Catalin Marinas
<catalin.marinas@arm.com> wrote:
> From: Catalin Marinas <catalin.marinas@arm.com>
>
> Commit 246cf9c26b introduced the tracking of direct dependency to
> provide additional warning when they are not met. With some complex
> dependencies, the expr_copy() function called on such expressions may
> cause stack exhaustion. The patch removes the superfluous expr_copy()
> call since expr_transform handles symbol duplication already.
>
I'm afraid this is just moving the problem from expr_copy() to
expr_transform() as the first thing the latter do is to recurse. on
the sub-expressions. I'm not sure that the expression causing the
stack exhaustion is even correct, or its reference is still valid.

 - Arnaud

> Signed-off-by: Catalin Marinas <catalin.marinas@arm.com>
> Reported-by: Arnaud Lacombe <lacombar@gmail.com>
> ---
>  scripts/kconfig/menu.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
>
> diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
> index 4fb5902..7298806 100644
> --- a/scripts/kconfig/menu.c
> +++ b/scripts/kconfig/menu.c
> @@ -292,7 +292,7 @@ void menu_finalize(struct menu *parent)
>                        menu_finalize(menu);
>        } else if (sym) {
>                /* ignore inherited dependencies for dir_dep */
> -               sym->dir_dep.expr = expr_transform(expr_copy(parent->dir_dep));
> +               sym->dir_dep.expr = expr_transform(parent->dir_dep);
>                sym->dir_dep.expr = expr_eliminate_dups(sym->dir_dep.expr);
>
>                basedep = parent->prompt ? parent->prompt->visible.expr : NULL;
>
>
> --
> Catalin
>
>

Re: Stale expression reference causing use-after-free

[Catalin Marinas]

Arnaud Lacombe <lacombar@gmail.com> wrote:
> On Tue, Sep 21, 2010 at 8:32 AM, Catalin Marinas
> <catalin.marinas@arm.com> wrote:
>> From: Catalin Marinas <catalin.marinas@arm.com>
>>
>> Commit 246cf9c26b introduced the tracking of direct dependency to
>> provide additional warning when they are not met. With some complex
>> dependencies, the expr_copy() function called on such expressions may
>> cause stack exhaustion. The patch removes the superfluous expr_copy()
>> call since expr_transform handles symbol duplication already.
>
> I'm afraid this is just moving the problem from expr_copy() to
> expr_transform() as the first thing the latter do is to recurse. on
> the sub-expressions. I'm not sure that the expression causing the
> stack exhaustion is even correct, or its reference is still valid.

It may actually be just accessing freed symbols and the data being
corrupted in ends up in a loop. You Kconfig example doesn't seem to have
any dependency loops that would cause such problems.

Does the patch below make it any better (together with the previous
one)?


diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
index 7298806..e707aa2 100644
--- a/scripts/kconfig/menu.c
+++ b/scripts/kconfig/menu.c
@@ -107,7 +107,9 @@ static struct expr *menu_check_dep(struct expr *e)
 void menu_add_dep(struct expr *dep)
 {
 	current_entry->dep = expr_alloc_and(current_entry->dep, menu_check_dep(dep));
-	current_entry->dir_dep = current_entry->dep;
+	if (current_entry->dir_dep)
+		expr_free(current_entry->dir_dep);
+	current_entry->dir_dep = expr_copy(current_entry->dep);
 }
 
 void menu_set_type(int type)


Thanks.

-- 
Catalin

Re: Stale expression reference causing use-after-free

[Arnaud Lacombe]

Hi,

On Tue, Sep 21, 2010 at 12:22 PM, Catalin Marinas
<catalin.marinas@arm.com> wrote:
> Arnaud Lacombe <lacombar@gmail.com> wrote:
>> On Tue, Sep 21, 2010 at 8:32 AM, Catalin Marinas
>> <catalin.marinas@arm.com> wrote:
>>> From: Catalin Marinas <catalin.marinas@arm.com>
>>>
>>> Commit 246cf9c26b introduced the tracking of direct dependency to
>>> provide additional warning when they are not met. With some complex
>>> dependencies, the expr_copy() function called on such expressions may
>>> cause stack exhaustion. The patch removes the superfluous expr_copy()
>>> call since expr_transform handles symbol duplication already.
>>
>> I'm afraid this is just moving the problem from expr_copy() to
>> expr_transform() as the first thing the latter do is to recurse. on
>> the sub-expressions. I'm not sure that the expression causing the
>> stack exhaustion is even correct, or its reference is still valid.
>
> It may actually be just accessing freed symbols and the data being
> corrupted in ends up in a loop. You Kconfig example doesn't seem to have
> any dependency loops that would cause such problems.
>
exactly.

> Does the patch below make it any better (together with the previous
> one)?
>
just this one is enough. I added back the memory poisoning in
expr_free() and did not get any message of invalid expression.

Michal, should all the weak warning "can't copy/free expr" be replaced
by more aggressive abort() by dropping a few EXPR_CHECK() in expr.c ?

>
> diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
> index 7298806..e707aa2 100644
> --- a/scripts/kconfig/menu.c
> +++ b/scripts/kconfig/menu.c
> @@ -107,7 +107,9 @@ static struct expr *menu_check_dep(struct expr *e)
>  void menu_add_dep(struct expr *dep)
>  {
>        current_entry->dep = expr_alloc_and(current_entry->dep, menu_check_dep(dep));
> -       current_entry->dir_dep = current_entry->dep;
> +       if (current_entry->dir_dep)
> +               expr_free(current_entry->dir_dep);
the test is not needed, expr_free() will return immediately if (e == NULL).

> +       current_entry->dir_dep = expr_copy(current_entry->dep);
FYI, just this line makes the crash disappear, still I understand the
expr_free(). However, wouldn't there be a better place to initialize
`dir_dep' and avoid the need to use expr_free() ?

Thanks,
 - Arnaud

Re: Stale expression reference causing use-after-free

[Catalin Marinas]

Arnaud Lacombe <lacombar@gmail.com> wrote:
> On Tue, Sep 21, 2010 at 12:22 PM, Catalin Marinas
> <catalin.marinas@arm.com> wrote:
>> Arnaud Lacombe <lacombar@gmail.com> wrote:
>>> On Tue, Sep 21, 2010 at 8:32 AM, Catalin Marinas
>>> <catalin.marinas@arm.com> wrote:
>>>> From: Catalin Marinas <catalin.marinas@arm.com>
>>>>
>>>> Commit 246cf9c26b introduced the tracking of direct dependency to
>>>> provide additional warning when they are not met. With some complex
>>>> dependencies, the expr_copy() function called on such expressions may
>>>> cause stack exhaustion. The patch removes the superfluous expr_copy()
>>>> call since expr_transform handles symbol duplication already.
[...]
>> Does the patch below make it any better (together with the previous
>> one)?
>>
> just this one is enough. I added back the memory poisoning in
> expr_free() and did not get any message of invalid expression.

Thanks for testing. I would add the other patch as well, maybe as a
separate one since it's a clean-up.

>> diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
>> index 7298806..e707aa2 100644
>> --- a/scripts/kconfig/menu.c
>> +++ b/scripts/kconfig/menu.c
>> @@ -107,7 +107,9 @@ static struct expr *menu_check_dep(struct expr *e)
>>  void menu_add_dep(struct expr *dep)
>>  {
>>        current_entry->dep = expr_alloc_and(current_entry->dep, menu_check_dep(dep));
>> -       current_entry->dir_dep = current_entry->dep;
>> +       if (current_entry->dir_dep)
>> +               expr_free(current_entry->dir_dep);
> the test is not needed, expr_free() will return immediately if (e == NULL).
>
>> +       current_entry->dir_dep = expr_copy(current_entry->dep);
> 
> FYI, just this line makes the crash disappear, still I understand the
> expr_free(). However, wouldn't there be a better place to initialize
> `dir_dep' and avoid the need to use expr_free() ?

dir_dep would need to be initialised somewhere, unless there is a memset
on the whole structure (I'm not familiar enough with kbuild). But I
think we still need the expr_free() in case dir_dep gets overwritten
(e.g. multiple 'depends on' lines where the full expression is re-built
on the previous line via expr_alloc_and()).

I'll post some patches tomorrow to be reviewed (have to go now).

-- 
Catalin

Re: Stale expression reference causing use-after-free

[Arnaud Lacombe]

Hi,

On Tue, Sep 21, 2010 at 12:55 PM, Catalin Marinas
<catalin.marinas@arm.com> wrote:
> Arnaud Lacombe <lacombar@gmail.com> wrote:
>> FYI, just this line makes the crash disappear, still I understand the
>> expr_free(). However, wouldn't there be a better place to initialize
>> `dir_dep' and avoid the need to use expr_free() ?
>
> dir_dep would need to be initialised somewhere, unless there is a memset
> on the whole structure (I'm not familiar enough with kbuild). But I
> think we still need the expr_free() in case dir_dep gets overwritten
> (e.g. multiple 'depends on' lines where the full expression is re-built
> on the previous line via expr_alloc_and()).
>
this is a huge shoot in the dark, but does not seem to cause any regression:

diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
index 23acbdb..9eee093 100644
--- a/scripts/kconfig/menu.c
+++ b/scripts/kconfig/menu.c
@@ -107,7 +107,6 @@ static struct expr *menu_check_dep(struct expr *e)
 void menu_add_dep(struct expr *dep)
 {
        current_entry->dep = expr_alloc_and(current_entry->dep,
menu_check_dep(dep));
-       current_entry->dir_dep = current_entry->dep;
 }

 void menu_set_type(int type)
@@ -268,6 +267,7 @@ void menu_finalize(struct menu *parent)
                        basedep = expr_alloc_and(expr_copy(parentdep), basedep);
                        basedep = expr_eliminate_dups(basedep);
                        menu->dep = basedep;
+                       menu->dir_dep = expr_copy(basedep);
                        if (menu->sym)
                                prop = menu->sym->prop;
                        else


 - Arnaud

Re: Stale expression reference causing use-after-free

[Catalin Marinas]

On Tue, 2010-09-21 at 12:57 -0400, Arnaud Lacombe wrote:
> On Tue, Sep 21, 2010 at 12:55 PM, Catalin Marinas
> <catalin.marinas@arm.com> wrote:
> > Arnaud Lacombe <lacombar@gmail.com> wrote:
> >> FYI, just this line makes the crash disappear, still I understand the
> >> expr_free(). However, wouldn't there be a better place to initialize
> >> `dir_dep' and avoid the need to use expr_free() ?
> >
> > dir_dep would need to be initialised somewhere, unless there is a memset
> > on the whole structure (I'm not familiar enough with kbuild). But I
> > think we still need the expr_free() in case dir_dep gets overwritten
> > (e.g. multiple 'depends on' lines where the full expression is re-built
> > on the previous line via expr_alloc_and()).
> 
> this is a huge shoot in the dark, but does not seem to cause any regression:
> 
> diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
> index 23acbdb..9eee093 100644
> --- a/scripts/kconfig/menu.c
> +++ b/scripts/kconfig/menu.c
> @@ -107,7 +107,6 @@ static struct expr *menu_check_dep(struct expr *e)
>  void menu_add_dep(struct expr *dep)
>  {
>         current_entry->dep = expr_alloc_and(current_entry->dep, menu_check_dep(dep));
> -       current_entry->dir_dep = current_entry->dep;
>  }
> 
>  void menu_set_type(int type)
> @@ -268,6 +267,7 @@ void menu_finalize(struct menu *parent)
>                         basedep = expr_alloc_and(expr_copy(parentdep), basedep);
>                         basedep = expr_eliminate_dups(basedep);
>                         menu->dep = basedep;
> +                       menu->dir_dep = expr_copy(basedep);
>                         if (menu->sym)
>                                 prop = menu->sym->prop;
>                         else

I'm not sure this would have the same effect as what I intended. The
dir_dep should only store the "depends on" clauses but the basedep at
this point may include some "select" clauses as well.

Thinking about it, my original patch may not be fully correct. Maybe
something like below:


diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
index 7298806..e43d8d0 100644
--- a/scripts/kconfig/menu.c
+++ b/scripts/kconfig/menu.c
@@ -107,7 +107,8 @@ static struct expr *menu_check_dep(struct expr *e)
 void menu_add_dep(struct expr *dep)
 {
 	current_entry->dep = expr_alloc_and(current_entry->dep, menu_check_dep(dep));
-	current_entry->dir_dep = current_entry->dep;
+	current_entry->dir_dep = expr_alloc_and(current_entry->dir_dep,
+						menu_check_dep(dep));
 }
 
 void menu_set_type(int type)


-- 
Catalin

Re: Stale expression reference causing use-after-free

[Arnaud Lacombe]

Hi,

On Tue, Sep 21, 2010 at 1:03 PM, Catalin Marinas
<catalin.marinas@arm.com> wrote:
> On Tue, 2010-09-21 at 12:57 -0400, Arnaud Lacombe wrote:
>> On Tue, Sep 21, 2010 at 12:55 PM, Catalin Marinas
>> <catalin.marinas@arm.com> wrote:
>> > Arnaud Lacombe <lacombar@gmail.com> wrote:
>> >> FYI, just this line makes the crash disappear, still I understand the
>> >> expr_free(). However, wouldn't there be a better place to initialize
>> >> `dir_dep' and avoid the need to use expr_free() ?
>> >
>> > dir_dep would need to be initialised somewhere, unless there is a memset
>> > on the whole structure (I'm not familiar enough with kbuild). But I
>> > think we still need the expr_free() in case dir_dep gets overwritten
>> > (e.g. multiple 'depends on' lines where the full expression is re-built
>> > on the previous line via expr_alloc_and()).
>>
>> this is a huge shoot in the dark, but does not seem to cause any regression:
>>
>> diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
>> index 23acbdb..9eee093 100644
>> --- a/scripts/kconfig/menu.c
>> +++ b/scripts/kconfig/menu.c
>> @@ -107,7 +107,6 @@ static struct expr *menu_check_dep(struct expr *e)
>>  void menu_add_dep(struct expr *dep)
>>  {
>>         current_entry->dep = expr_alloc_and(current_entry->dep, menu_check_dep(dep));
>> -       current_entry->dir_dep = current_entry->dep;
>>  }
>>
>>  void menu_set_type(int type)
>> @@ -268,6 +267,7 @@ void menu_finalize(struct menu *parent)
>>                         basedep = expr_alloc_and(expr_copy(parentdep), basedep);
>>                         basedep = expr_eliminate_dups(basedep);
>>                         menu->dep = basedep;
>> +                       menu->dir_dep = expr_copy(basedep);
>>                         if (menu->sym)
>>                                 prop = menu->sym->prop;
>>                         else
>
> I'm not sure this would have the same effect as what I intended. The
> dir_dep should only store the "depends on" clauses but the basedep at
> this point may include some "select" clauses as well.
>
I'm not sure of that. "select" statement are appended to the
(selected?) symbol property list and simplified after `basedep' has
been computed, before being assigned to the symbol reverse dependency.
So, as far as I understand, `basedep' dependency's list is free from
any reverse dependency. Maybe a kconfig's guru can confirm. That would
simplify a lot.

> Thinking about it, my original patch may not be fully correct. Maybe
> something like below:
>
>
> diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
> index 7298806..e43d8d0 100644
> --- a/scripts/kconfig/menu.c
> +++ b/scripts/kconfig/menu.c
> @@ -107,7 +107,8 @@ static struct expr *menu_check_dep(struct expr *e)
>  void menu_add_dep(struct expr *dep)
>  {
>        current_entry->dep = expr_alloc_and(current_entry->dep, menu_check_dep(dep));
> -       current_entry->dir_dep = current_entry->dep;
> +       current_entry->dir_dep = expr_alloc_and(current_entry->dir_dep,
> +                                               menu_check_dep(dep));
>  }
>
This alone re-introduce the use-after-free. I cannot really dig
further right now.

 - Arnaud

Re: Stale expression reference causing use-after-free

[Catalin Marinas]

On Tue, 2010-09-21 at 19:03 +0100, Arnaud Lacombe wrote:
> On Tue, Sep 21, 2010 at 1:03 PM, Catalin Marinas
> <catalin.marinas@arm.com> wrote:
> > On Tue, 2010-09-21 at 12:57 -0400, Arnaud Lacombe wrote:
> >> this is a huge shoot in the dark, but does not seem to cause any regression:
> >>
> >> diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
> >> index 23acbdb..9eee093 100644
> >> --- a/scripts/kconfig/menu.c
> >> +++ b/scripts/kconfig/menu.c
> >> @@ -107,7 +107,6 @@ static struct expr *menu_check_dep(struct expr *e)
> >>  void menu_add_dep(struct expr *dep)
> >>  {
> >>         current_entry->dep = expr_alloc_and(current_entry->dep, menu_check_dep(dep));
> >> -       current_entry->dir_dep = current_entry->dep;
> >>  }
> >>
> >>  void menu_set_type(int type)
> >> @@ -268,6 +267,7 @@ void menu_finalize(struct menu *parent)
> >>                         basedep = expr_alloc_and(expr_copy(parentdep), basedep);
> >>                         basedep = expr_eliminate_dups(basedep);
> >>                         menu->dep = basedep;
> >> +                       menu->dir_dep = expr_copy(basedep);
> >>                         if (menu->sym)
> >>                                 prop = menu->sym->prop;
> >>                         else
> >
> > I'm not sure this would have the same effect as what I intended. The
> > dir_dep should only store the "depends on" clauses but the basedep at
> > this point may include some "select" clauses as well.
> 
> I'm not sure of that. "select" statement are appended to the
> (selected?) symbol property list and simplified after `basedep' has
> been computed, before being assigned to the symbol reverse dependency.
> So, as far as I understand, `basedep' dependency's list is free from
> any reverse dependency. Maybe a kconfig's guru can confirm. That would
> simplify a lot.

You may be right. I did some tests and it looks like it indeed does the
trick (warning on selecting symbols with unmet dependencies). You can
submit it with my ack:

Acked-by: Catalin Marinas <catalin.marinas@arm.com>

In your patch, could you also remove the additional expr_copy() when
transforming dir_dep (my first patch which wasn't solving the problem
but an extra copy is superfluous).

Thanks.

-- 
Catalin

Re: Stale expression reference causing use-after-free

[Arnaud Lacombe]

Hi Catalin,

On Wed, Sep 22, 2010 at 7:08 AM, Catalin Marinas
<catalin.marinas@arm.com> wrote:
> In your patch, could you also remove the additional expr_copy() when
> transforming dir_dep (my first patch which wasn't solving the problem
> but an extra copy is superfluous).
>
isn't there more superfluous stuff ? The following:

diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c
index 4fb5902..176618a 100644
--- a/scripts/kconfig/menu.c
+++ b/scripts/kconfig/menu.c
@@ -107,7 +107,6 @@ static struct expr *menu_check_dep(struct expr *e)
 void menu_add_dep(struct expr *dep)
 {
        current_entry->dep = expr_alloc_and(current_entry->dep,
menu_check_dep(dep));
-       current_entry->dir_dep = current_entry->dep;
 }

 void menu_set_type(int type)
@@ -292,8 +291,7 @@ void menu_finalize(struct menu *parent)
                        menu_finalize(menu);
        } else if (sym) {
                /* ignore inherited dependencies for dir_dep */
-               sym->dir_dep.expr = expr_transform(expr_copy(parent->dir_dep));
-               sym->dir_dep.expr = expr_eliminate_dups(sym->dir_dep.expr);
+               sym->dir_dep = parent->dep;

                basedep = parent->prompt ? parent->prompt->visible.expr : NULL;
                basedep = expr_trans_compare(basedep, E_UNEQUAL, &symbol_no);


still seems not to introduce regression, ie. same output with
`silentoldconfig' based on a `randconfig' with this or with the
previous I submitted. The
"expr_eliminate_dups(expr_transform(parent->dep))" has already been
done when computing `basedep'.

Thanks,
 - Arnaud

Re: Stale expression reference causing use-after-free

[Catalin Marinas]

On Wed, 2010-09-22 at 18:32 +0100, Arnaud Lacombe wrote:
> On Wed, Sep 22, 2010 at 7:08 AM, Catalin Marinas
> <catalin.marinas@arm.com> wrote:
> > In your patch, could you also remove the additional expr_copy() when
> > transforming dir_dep (my first patch which wasn't solving the problem
> > but an extra copy is superfluous).
> 
> isn't there more superfluous stuff ? The following:
[...]
> @@ -292,8 +291,7 @@ void menu_finalize(struct menu *parent)
>                         menu_finalize(menu);
>         } else if (sym) {
>                 /* ignore inherited dependencies for dir_dep */
> -               sym->dir_dep.expr = expr_transform(expr_copy(parent->dir_dep));
> -               sym->dir_dep.expr = expr_eliminate_dups(sym->dir_dep.expr);
> +               sym->dir_dep = parent->dep;

With this change I get:

/work/Linux/linux-2.6-arm/scripts/kconfig/menu.c: In function ‘menu_finalize’:
/work/Linux/linux-2.6-arm/scripts/kconfig/menu.c:301: error: incompatible types 
	when assigning to type ‘struct expr_value’ from type ‘struct expr *’

-- 
Catalin