| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Mon, 24 Jun 2013 20:11:56 +0200
From: "Yann E. MORIN" <yann.morin.1998@...e.fr>
To: linux-kbuild@...r.kernel.org
Cc: linux-kernel@...r.kernel.org, Michal Marek <mmarek@...e.cz>,
"Yann E. MORIN" <yann.morin.1998@...e.fr>,
Jean Delvare <jdelvare@...e.de>,
Roland Eggner <edvx1@...temanalysen.net>,
Wang YanQing <udknight@...il.com>
Subject: [PATCH 12/15] kconfig: sort found symbols by relevance
From: "Yann E. MORIN" <yann.morin.1998@...e.fr>
When searching for symbols, return the symbols sorted by relevance.
Sorting is done as thus:
- first, symbols that match exactly
- then, alphabetical sort
Since the search can be a regexp, it is possible that more than one symbol
matches exactly. In this case, we can't decide which to sort first, so we
fallback to alphabeticall sort.
Explain this (new!) sorting heuristic in the documentation.
Reported-by: Jean Delvare <jdelvare@...e.de>
Signed-off-by: "Yann E. MORIN" <yann.morin.1998@...e.fr>
Cc: Jean Delvare <jdelvare@...e.de>
Cc: Michal Marek <mmarek@...e.cz>
Cc: Roland Eggner <edvx1@...temanalysen.net>
Cc: Wang YanQing <udknight@...il.com>
--
Changes v1->v2:
- drop the previous, complex heuristic in favour of a simpler heuristic
that is both easier to understand, *and* to maintain (Jean)
- explain sorting heuristic in the doc (Jean)
---
Documentation/kbuild/kconfig.txt | 13 +++++++
scripts/kconfig/symbol.c | 78 +++++++++++++++++++++++++++++++++++-----
2 files changed, 82 insertions(+), 9 deletions(-)
diff --git a/Documentation/kbuild/kconfig.txt b/Documentation/kbuild/kconfig.txt
index 3f429ed..e9f9e76 100644
--- a/Documentation/kbuild/kconfig.txt
+++ b/Documentation/kbuild/kconfig.txt
@@ -174,6 +174,19 @@ Searching in menuconfig:
/^hotplug
+ When searching, symbols are sorted thus:
+ - exact match first: an exact match is when the search matches
+ the complete symbol name;
+ - alphabetical order: when two symbols do not match exactly,
+ they are sorted in alphabetical order (in the user's current
+ locale).
+ For example: ^ATH.K matches:
+ ATH5K ATH9K ATH5K_AHB ATH5K_DEBUG [...] ATH6KL ATH6KL_DEBUG
+ [...] ATH9K_AHB ATH9K_BTCOEX_SUPPORT ATH9K_COMMON [...]
+ of which only ATH5K and ATH9K match exactly and so are sorted
+ first (and in alphabetical order), then come all other symbols,
+ sorted in alphabetical order.
+
______________________________________________________________________
User interface options for 'menuconfig'
diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c
index ab8f4c8..387d554 100644
--- a/scripts/kconfig/symbol.c
+++ b/scripts/kconfig/symbol.c
@@ -954,38 +954,98 @@ const char *sym_escape_string_value(const char *in)
return res;
}
+struct sym_match {
+ struct symbol *sym;
+ off_t so, eo;
+};
+
+/* Compare matched symbols as thus:
+ * - first, symbols that match exactly
+ * - then, alphabetical sort
+ */
+static int sym_rel_comp( const void *sym1, const void *sym2 )
+{
+ struct sym_match *s1 = *(struct sym_match **)sym1;
+ struct sym_match *s2 = *(struct sym_match **)sym2;
+ int l1, l2;
+
+ /* Exact match:
+ * - if matched length on symbol s1 is the length of that symbol,
+ * then this symbol should come first;
+ * - if matched length on symbol s2 is the length of that symbol,
+ * then this symbol should come first.
+ * Note: since the search can be a regexp, both symbols may match
+ * exactly; if this is the case, we can't decide which comes first,
+ * and we fallback to sorting alphabetically.
+ */
+ l1 = s1->eo - s1->so;
+ l2 = s2->eo - s2->so;
+ if (l1 == strlen(s1->sym->name) && l2 != strlen(s2->sym->name))
+ return -1;
+ if (l1 != strlen(s1->sym->name) && l2 == strlen(s2->sym->name))
+ return 1;
+
+ /* As a fallback, sort symbols alphabetically */
+ return strcmp(s1->sym->name, s2->sym->name);
+}
+
struct symbol **sym_re_search(const char *pattern)
{
struct symbol *sym, **sym_arr = NULL;
+ struct sym_match **sym_match_arr = NULL;
int i, cnt, size;
regex_t re;
+ regmatch_t match[1];
cnt = size = 0;
/* Skip if empty */
if (strlen(pattern) == 0)
return NULL;
- if (regcomp(&re, pattern, REG_EXTENDED|REG_NOSUB|REG_ICASE))
+ if (regcomp(&re, pattern, REG_EXTENDED|REG_ICASE))
return NULL;
for_all_symbols(i, sym) {
+ struct sym_match *tmp_sym_match;
if (sym->flags & SYMBOL_CONST || !sym->name)
continue;
- if (regexec(&re, sym->name, 0, NULL, 0))
+ if (regexec(&re, sym->name, 1, match, 0))
continue;
if (cnt + 1 >= size) {
- void *tmp = sym_arr;
+ void *tmp;
size += 16;
- sym_arr = realloc(sym_arr, size * sizeof(struct symbol *));
- if (!sym_arr) {
- free(tmp);
- return NULL;
+ tmp = realloc(sym_match_arr, size * sizeof(struct sym_match *));
+ if (!tmp) {
+ goto sym_re_search_free;
}
+ sym_match_arr = tmp;
}
sym_calc_value(sym);
- sym_arr[cnt++] = sym;
+ tmp_sym_match = (struct sym_match*)malloc(sizeof(struct sym_match));
+ if (!tmp_sym_match)
+ goto sym_re_search_free;
+ tmp_sym_match->sym = sym;
+ /* As regexec return 0, we know we have a match, so
+ * we can use match[0].rm_[se]o without further checks
+ */
+ tmp_sym_match->so = match[0].rm_so;
+ tmp_sym_match->eo = match[0].rm_eo;
+ sym_match_arr[cnt++] = tmp_sym_match;
}
- if (sym_arr)
+ if (sym_match_arr) {
+ qsort(sym_match_arr, cnt, sizeof(struct sym_match*), sym_rel_comp);
+ sym_arr = malloc((cnt+1) * sizeof(struct symbol));
+ if (!sym_arr)
+ goto sym_re_search_free;
+ for (i = 0; i < cnt; i++)
+ sym_arr[i] = sym_match_arr[i]->sym;
sym_arr[cnt] = NULL;
+ }
+sym_re_search_free:
+ if (sym_match_arr) {
+ for (i = 0; i < cnt; i++)
+ free(sym_match_arr[i]);
+ free(sym_match_arr);
+ }
regfree(&re);
return sym_arr;
--
1.8.1.2
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists