From 5b1374b3b3c2fc4f63a398adfa446fb8eff791a4 Mon Sep 17 00:00:00 2001 From: Ulf Magnusson Date: Sun, 8 Oct 2017 19:35:45 +0200 Subject: kconfig: Fix expr_free() E_NOT leak Only the E_NOT operand and not the E_NOT node itself was freed, due to accidentally returning too early in expr_free(). Outline of leak: switch (e->type) { ... case E_NOT: expr_free(e->left.expr); return; ... } *Never reached, 'e' leaked* free(e); Fix by changing the 'return' to a 'break'. Summary from Valgrind on 'menuconfig' (ARCH=x86) before the fix: LEAK SUMMARY: definitely lost: 44,448 bytes in 1,852 blocks ... Summary after the fix: LEAK SUMMARY: definitely lost: 1,608 bytes in 67 blocks ... Signed-off-by: Ulf Magnusson Signed-off-by: Masahiro Yamada --- scripts/kconfig/expr.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'scripts/kconfig/expr.c') diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c index cbf4996dd9c1..ed29bad1f03a 100644 --- a/scripts/kconfig/expr.c +++ b/scripts/kconfig/expr.c @@ -113,7 +113,7 @@ void expr_free(struct expr *e) break; case E_NOT: expr_free(e->left.expr); - return; + break; case E_EQUAL: case E_GEQ: case E_GTH: -- cgit v1.2.3 From 0735f7e5def2ab4158aac8d35f3661e8819dc232 Mon Sep 17 00:00:00 2001 From: Ulf Magnusson Date: Sun, 8 Oct 2017 19:50:55 +0200 Subject: kconfig: Document important expression functions Many of these functions are quite the head scratchers if you don't know what they're trying to do. Document them. Also make it clear which functions rewrite expressions in-place and which return new expressions. This prevents memory errors. No functional changes. Only comments added. Signed-off-by: Ulf Magnusson Signed-off-by: Masahiro Yamada --- scripts/kconfig/expr.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 106 insertions(+) (limited to 'scripts/kconfig/expr.c') diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c index ed29bad1f03a..fd8a416ceab7 100644 --- a/scripts/kconfig/expr.c +++ b/scripts/kconfig/expr.c @@ -138,8 +138,18 @@ static int trans_count; #define e1 (*ep1) #define e2 (*ep2) +/* + * expr_eliminate_eq() helper. + * + * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does + * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared + * against all other leaves. Two equal leaves are both replaced with either 'y' + * or 'n' as appropriate for 'type', to be eliminated later. + */ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2) { + /* Recurse down to leaves */ + if (e1->type == type) { __expr_eliminate_eq(type, &e1->left.expr, &e2); __expr_eliminate_eq(type, &e1->right.expr, &e2); @@ -150,12 +160,18 @@ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct e __expr_eliminate_eq(type, &e1, &e2->right.expr); return; } + + /* e1 and e2 are leaves. Compare them. */ + if (e1->type == E_SYMBOL && e2->type == E_SYMBOL && e1->left.sym == e2->left.sym && (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no)) return; if (!expr_eq(e1, e2)) return; + + /* e1 and e2 are equal leaves. Prepare them for elimination. */ + trans_count++; expr_free(e1); expr_free(e2); switch (type) { @@ -172,6 +188,35 @@ static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct e } } +/* + * Rewrites the expressions 'ep1' and 'ep2' to remove operands common to both. + * Example reductions: + * + * ep1: A && B -> ep1: y + * ep2: A && B && C -> ep2: C + * + * ep1: A || B -> ep1: n + * ep2: A || B || C -> ep2: C + * + * ep1: A && (B && FOO) -> ep1: FOO + * ep2: (BAR && B) && A -> ep2: BAR + * + * ep1: A && (B || C) -> ep1: y + * ep2: (C || B) && A -> ep2: y + * + * Comparisons are done between all operands at the same "level" of && or ||. + * For example, in the expression 'e1 && (e2 || e3) && (e4 || e5)', the + * following operands will be compared: + * + * - 'e1', 'e2 || e3', and 'e4 || e5', against each other + * - e2 against e3 + * - e4 against e5 + * + * Parentheses are irrelevant within a single level. 'e1 && (e2 && e3)' and + * '(e1 && e2) && e3' are both a single level. + * + * See __expr_eliminate_eq() as well. + */ void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) { if (!e1 || !e2) @@ -197,6 +242,12 @@ void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) #undef e1 #undef e2 +/* + * Returns true if 'e1' and 'e2' are equal, after minor simplification. Two + * &&/|| expressions are considered equal if every operand in one expression + * equals some operand in the other (operands do not need to appear in the same + * order), recursively. + */ static int expr_eq(struct expr *e1, struct expr *e2) { int res, old_count; @@ -243,6 +294,17 @@ static int expr_eq(struct expr *e1, struct expr *e2) return 0; } +/* + * Recursively performs the following simplifications in-place (as well as the + * corresponding simplifications with swapped operands): + * + * expr && n -> n + * expr && y -> expr + * expr || n -> expr + * expr || y -> y + * + * Returns the optimized expression. + */ static struct expr *expr_eliminate_yn(struct expr *e) { struct expr *tmp; @@ -516,12 +578,21 @@ static struct expr *expr_join_and(struct expr *e1, struct expr *e2) return NULL; } +/* + * expr_eliminate_dups() helper. + * + * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does + * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared + * against all other leaves to look for simplifications. + */ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2) { #define e1 (*ep1) #define e2 (*ep2) struct expr *tmp; + /* Recurse down to leaves */ + if (e1->type == type) { expr_eliminate_dups1(type, &e1->left.expr, &e2); expr_eliminate_dups1(type, &e1->right.expr, &e2); @@ -532,6 +603,9 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr_eliminate_dups1(type, &e1, &e2->right.expr); return; } + + /* e1 and e2 are leaves. Compare and process them. */ + if (e1 == e2) return; @@ -568,6 +642,17 @@ static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct #undef e2 } +/* + * Rewrites 'e' in-place to remove ("join") duplicate and other redundant + * operands. + * + * Example simplifications: + * + * A || B || A -> A || B + * A && B && A=y -> A=y && B + * + * Returns the deduplicated expression. + */ struct expr *expr_eliminate_dups(struct expr *e) { int oldcount; @@ -584,6 +669,7 @@ struct expr *expr_eliminate_dups(struct expr *e) ; } if (!trans_count) + /* No simplifications done in this pass. We're done */ break; e = expr_eliminate_yn(e); } @@ -591,6 +677,12 @@ struct expr *expr_eliminate_dups(struct expr *e) return e; } +/* + * Performs various simplifications involving logical operators and + * comparisons. + * + * Allocates and returns a new expression. + */ struct expr *expr_transform(struct expr *e) { struct expr *tmp; @@ -805,6 +897,20 @@ bool expr_depends_symbol(struct expr *dep, struct symbol *sym) return false; } +/* + * Inserts explicit comparisons of type 'type' to symbol 'sym' into the + * expression 'e'. + * + * Examples transformations for type == E_UNEQUAL, sym == &symbol_no: + * + * A -> A!=n + * !A -> A=n + * A && B -> !(A=n || B=n) + * A || B -> !(A=n && B=n) + * A && (B || C) -> !(A=n || (B=n && C=n)) + * + * Allocates and returns a new expression. + */ struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym) { struct expr *e1, *e2; -- cgit v1.2.3 From 1ccb27143360bd2390a9a970e50709f858b53761 Mon Sep 17 00:00:00 2001 From: Petr Vorel Date: Thu, 25 Jan 2018 10:46:35 +0100 Subject: kconfig: make "Selected by:" and "Implied by:" readable Reverse dependency expressions can get rather unwieldy, especially if a symbol is selected by more than a handful of other symbols. I.e. it's possible to have near endless expressions like: A && B && !C || D || F && (G || H) || [...] Chop these expressions into actually readable chunks: - A && B && !C - D - F && (G || H) - [...] I.e. transform the top level OR tokens into newlines and prepend each line with a minus. This makes the "Selected by:" and "Implied by:" blurb much easier to read. This is done only if there is more than one top level OR. "Depends on:" and "Range :" were deliberately left as they are. Based on idea from Paul Bolle. Suggested-by: Paul Bolle Signed-off-by: Petr Vorel Signed-off-by: Masahiro Yamada --- scripts/kconfig/expr.c | 28 ++++++++++++++++++++++++---- 1 file changed, 24 insertions(+), 4 deletions(-) (limited to 'scripts/kconfig/expr.c') diff --git a/scripts/kconfig/expr.c b/scripts/kconfig/expr.c index fd8a416ceab7..04fa71e058b7 100644 --- a/scripts/kconfig/expr.c +++ b/scripts/kconfig/expr.c @@ -1176,7 +1176,7 @@ struct expr *expr_simplify_unmet_dep(struct expr *e1, struct expr *e2) return expr_get_leftmost_symbol(ret); } -void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken) +static void __expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken, bool revdep) { if (!e) { fn(data, NULL, "y"); @@ -1231,9 +1231,14 @@ void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char * fn(data, e->right.sym, e->right.sym->name); break; case E_OR: - expr_print(e->left.expr, fn, data, E_OR); - fn(data, NULL, " || "); - expr_print(e->right.expr, fn, data, E_OR); + if (revdep && e->left.expr->type != E_OR) + fn(data, NULL, "\n - "); + __expr_print(e->left.expr, fn, data, E_OR, revdep); + if (revdep) + fn(data, NULL, "\n - "); + else + fn(data, NULL, " || "); + __expr_print(e->right.expr, fn, data, E_OR, revdep); break; case E_AND: expr_print(e->left.expr, fn, data, E_AND); @@ -1266,6 +1271,11 @@ void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char * fn(data, NULL, ")"); } +void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken) +{ + __expr_print(e, fn, data, prevtoken, false); +} + static void expr_print_file_helper(void *data, struct symbol *sym, const char *str) { xfwrite(str, strlen(str), 1, data); @@ -1310,3 +1320,13 @@ void expr_gstr_print(struct expr *e, struct gstr *gs) { expr_print(e, expr_print_gstr_helper, gs, E_NONE); } + +/* + * Transform the top level "||" tokens into newlines and prepend each + * line with a minus. This makes expressions much easier to read. + * Suitable for reverse dependency expressions. + */ +void expr_gstr_print_revdep(struct expr *e, struct gstr *gs) +{ + __expr_print(e, expr_print_gstr_helper, gs, E_NONE, true); +} -- cgit v1.2.3