ACK: [PATCH 1/3] kernelscan: speed up parser using hash lookup, add more print funcs
Alex Hung
alex.hung at canonical.com
Fri Apr 29 08:39:32 UTC 2016
On 2016-04-27 05:53 PM, Colin King wrote:
> From: Colin Ian King <colin.king at canonical.com>
>
> Adding a hash lookup that is self optimizing to a 1-to-1 lookup on
> a larger range of kernel print functions not only speeds up the parsing
> function comparison, but also allows us to add more functions to compare
> with for a broader search.
>
> Signed-off-by: Colin Ian King <colin.king at canonical.com>
> ---
> src/utilities/kernelscan.c | 176 +++++++++++++++++++++++++++++++++++----------
> 1 file changed, 138 insertions(+), 38 deletions(-)
>
> diff --git a/src/utilities/kernelscan.c b/src/utilities/kernelscan.c
> index 516577c..3a78ff7 100644
> --- a/src/utilities/kernelscan.c
> +++ b/src/utilities/kernelscan.c
> @@ -109,8 +109,102 @@ typedef struct {
> */
> static klog_pattern *patterns;
>
> +static unsigned int hash_size;
> +
> +static char *funcs[] = {
> + "printk",
> + "printf",
> + "early_printk",
> + "vprintk_emit",
> + "vprintk",
> + "printk_emit",
> + "printk_once",
> + "printk_deferred",
> + "printk_deferred_once",
> + "pr_emerg",
> + "pr_alert",
> + "pr_crit",
> + "pr_err",
> + "pr_warning",
> + "pr_warn",
> + "pr_notice",
> + "pr_info",
> + "pr_cont",
> + "pr_devel",
> + "pr_debug",
> + "pr_emerg_once",
> + "pr_alert_once",
> + "pr_crit_once",
> + "pr_err_once",
> + "pr_warning_once",
> + "pr_warn_once",
> + "pr_notice_once",
> + "pr_info_once",
> + "pr_cont_once",
> + "pr_devel_once",
> + "pr_debug_once",
> + "dynamic_pr_debug",
> + "dev_vprintk_emit",
> + "dev_printk_emit",
> + "dev_printk",
> + "dev_emerg",
> + "dev_alert",
> + "dev_crit",
> + "dev_err",
> + "dev_warn",
> + "dev_dbg",
> + "dev_notice",
> + "dev_level_once",
> + "dev_emerg_once",
> + "dev_alert_once",
> + "dev_crit_once",
> + "dev_err_once",
> + "dev_warn_once",
> + "dev_notice_once",
> + "dev_info_once",
> + "dev_dbg_once",
> + "dev_level_ratelimited",
> + "dev_emerg_ratelimited",
> + "dev_alert_ratelimited",
> + "dev_crit_ratelimited",
> + "dev_err_ratelimited",
> + "dev_warn_ratelimited",
> + "dev_notice_ratelimited",
> + "dev_info_ratelimited",
> + "dbg",
> + "ACPI_ERROR",
> + "ACPI_INFO",
> + "ACPI_WARNING",
> + "ACPI_EXCEPTION",
> + "ACPI_BIOS_WARNING",
> + "ACPI_BIOS_ERROR",
> + "ACPI_ERROR_METHOD",
> + /*
> + "ACPI_DEBUG_PRINT",
> + "ACPI_DEBUG_PRINT_RAW",
> + "DEBUG",
> + */
> + NULL
> +};
> +
> +#define TABLE_SIZE (5000)
> +
> +static char *hash_funcs[TABLE_SIZE];
> +
> static int get_token(parser *p, token *t);
>
> +static inline unsigned int djb2a(const char *str)
> +{
> + register unsigned int hash = 5381;
> + register unsigned int c;
> +
> + while ((c = *str++)) {
> + /* (hash * 33) ^ c */
> + hash = ((hash << 5) + hash) ^ c;
> + }
> + return hash;
> +}
> +
> /*
> * Initialise the parser
> */
> @@ -784,21 +878,10 @@ static char *strdupcat(char *old, char *new)
> static int parse_kernel_message(parser *p, token *t)
> {
> bool got_string = false;
> - bool emit = false;
> bool found = false;
> token_type prev_token_type = TOKEN_UNKNOWN;
> char *str = NULL;
> char *line = NULL;
> - bool printk;
> -
> - printk = (strcmp(t->token, "printk") == 0);
> -
> - if ((strcmp(t->token, "dev_err") == 0) ||
> - (strcmp(t->token, "ACPI_ERROR") == 0) ||
> - (strcmp(t->token, "ACPI_BIOS_ERROR") == 0) ||
> - (strcmp(t->token, "ACPI_EXCEPTION") == 0) ||
> - (strcmp(t->token, "ACPI_ERROR_METHOD") == 0))
> - emit = true;
>
> line = strdupcat(line, t->token);
> token_clear(t);
> @@ -815,32 +898,16 @@ static int parse_kernel_message(parser *p, token *t)
> * Hit ; so lets push out what we've parsed
> */
> if (t->type == TOKEN_TERMINAL) {
> - if (emit) {
> - if (found) {
> - printf("OK : %s\n", line);
> - } else {
> - printf("ADD: %s\n", line);
> - }
> + if (found) {
> + printf("OK : %s\n", line);
> + } else {
> + printf("ADD: %s\n", line);
> }
> free(line);
> free(str);
> return PARSER_OK;
> }
>
> - /*
> - * We are only interested in KERN_ERR
> - * printk messages
> - */
> - if (printk &&
> - (t->type == TOKEN_IDENTIFIER) &&
> - (prev_token_type == TOKEN_PAREN_OPENED) &&
> - ((strcmp(t->token, "KERN_ERR") == 0) ||
> - (strcmp(t->token, "KERN_CRIT") == 0) ||
> - (strcmp(t->token, "KERN_EMERG") == 0) ||
> - (strcmp(t->token, "KERN_WARNING") == 0))) {
> - emit = true;
> - }
> -
> if (t->type == TOKEN_LITERAL_STRING) {
> literal_strip_quotes(t);
> str = strdupcat(str, t->token);
> @@ -877,6 +944,14 @@ static int parse_kernel_message(parser *p, token *t)
> free(line);
> }
>
> +static bool hash_find(char *token)
> +{
> + unsigned int h = djb2a(token) % hash_size;
> + char *hf = hash_funcs[h];
> +
> + return (hf && !strcmp(token, hf));
> +}
> +
> /*
> * Parse input looking for printk or dev_err calls
> */
> @@ -892,14 +967,9 @@ static void parse_kernel_messages(FILE *fp)
> token_new(&t);
>
> while ((get_token(&p, &t)) != EOF) {
> - if ((strcmp(t.token, "printk") == 0) ||
> - (strcmp(t.token, "dev_err") == 0) ||
> - (strcmp(t.token, "ACPI_ERROR") == 0) ||
> - (strcmp(t.token, "ACPI_BIOS_ERROR") == 0) ||
> - (strcmp(t.token, "ACPI_EXCEPTION") == 0) ||
> - (strcmp(t.token, "ACPI_ERROR_METHOD") == 0)) {
> + if (hash_find(t.token))
> parse_kernel_message(&p, &t);
> - } else
> + else
> token_clear(&t);
> }
>
> @@ -992,6 +1062,35 @@ static int parse_cpp_includes(FILE *fp)
> return EOF;
> }
>
> +
> +static void hash_init(void)
> +{
> + size_t i;
> +
> + /* Find optimal hash table size */
> + for (hash_size = 50; hash_size < TABLE_SIZE; hash_size++) {
> + bool collision = false;
> +
> + memset(hash_funcs, 0, sizeof(hash_funcs));
> +
> + for (i = 0; funcs[i]; i++) {
> + unsigned int h = djb2a(funcs[i]) % hash_size;
> +
> + if (hash_funcs[h]) {
> + collision = true;
> + break;
> + }
> + hash_funcs[h] = funcs[i];
> + }
> + if (!collision)
> + break;
> + }
> + if (hash_size == TABLE_SIZE) {
> + fprintf(stderr, "Increase TABLE_SIZE for hash table\n");
> + exit(EXIT_FAILURE);
> + }
> +}
> +
> /*
> * Scan kernel source for printk KERN_ERR and dev_err
> * calls.
> @@ -1025,6 +1124,7 @@ int main(int argc, char **argv)
> */
> if (strcmp(argv[1], "-P") == 0) {
> patterns = klog_load("firmware_error_warning_patterns");
> + hash_init();
> parse_kernel_messages(stdin);
> klog_free(patterns);
> }
>
Acked-by: Alex Hung <alex.hung at canonical.com>
More information about the fwts-devel
mailing list