diff options
Diffstat (limited to 'btparser/lib/backtrace.c')
-rw-r--r-- | btparser/lib/backtrace.c | 445 |
1 files changed, 445 insertions, 0 deletions
diff --git a/btparser/lib/backtrace.c b/btparser/lib/backtrace.c new file mode 100644 index 00000000..576c1776 --- /dev/null +++ b/btparser/lib/backtrace.c @@ -0,0 +1,445 @@ +/* + backtrace.c + + Copyright (C) 2010 Red Hat, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. +*/ +#include "backtrace.h" +#include "thread.h" +#include "frame.h" +#include "utils.h" +#include "strbuf.h" +#include "location.h" +#include "normalize.h" +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> + +struct btp_backtrace * +btp_backtrace_new() +{ + struct btp_backtrace *backtrace = btp_malloc(sizeof(struct btp_backtrace)); + btp_backtrace_init(backtrace); + return backtrace; +} + +void +btp_backtrace_init(struct btp_backtrace *backtrace) +{ + backtrace->threads = NULL; + backtrace->crash = NULL; +} + +void +btp_backtrace_free(struct btp_backtrace *backtrace) +{ + if (!backtrace) + return; + + while (backtrace->threads) + { + struct btp_thread *rm = backtrace->threads; + backtrace->threads = rm->next; + btp_thread_free(rm); + } + + if (backtrace->crash) + btp_frame_free(backtrace->crash); + + free(backtrace); +} + +struct btp_backtrace * +btp_backtrace_dup(struct btp_backtrace *backtrace) +{ + struct btp_backtrace *result = btp_backtrace_new(); + memcpy(result, backtrace, sizeof(struct btp_backtrace)); + + if (backtrace->crash) + backtrace->crash = btp_frame_dup(backtrace->crash, false); + if (backtrace->threads) + backtrace->threads = btp_thread_dup(backtrace->threads, true); + + return result; +} + +int +btp_backtrace_get_thread_count(struct btp_backtrace *backtrace) +{ + struct btp_thread *thread = backtrace->threads; + int count = 0; + while (thread) + { + thread = thread->next; + ++count; + } + return count; +} + +void +btp_backtrace_remove_threads_except_one(struct btp_backtrace *backtrace, + struct btp_thread *thread) +{ + while (backtrace->threads) + { + struct btp_thread *delete_thread = backtrace->threads; + backtrace->threads = delete_thread->next; + if (delete_thread != thread) + btp_thread_free(delete_thread); + } + + thread->next = NULL; + backtrace->threads = thread; +} + +/** + * Loop through all threads and if a single one contains the crash + * frame on the top, return it. Otherwise, return NULL. + * + * If require_abort is true, it is also required that the thread + * containing the crash frame contains some known "abort" function. In + * this case there can be multiple threads with the crash frame on the + * top, but only one of them might contain the abort function to + * succeed. + */ +static struct btp_thread * +btp_backtrace_find_crash_thread_from_crash_frame(struct btp_backtrace *backtrace, + bool require_abort) +{ + if (btp_debug_parser) + printf("%s(backtrace, %s)\n", __FUNCTION__, require_abort ? "true" : "false"); + + assert(backtrace->threads); /* checked by the caller */ + if (!backtrace->crash || !backtrace->crash->function_name) + return NULL; + + struct btp_thread *result = NULL; + struct btp_thread *thread = backtrace->threads; + while (thread) + { + struct btp_frame *top_frame = thread->frames; + bool same_name = top_frame && + top_frame->function_name && + 0 == strcmp(top_frame->function_name, backtrace->crash->function_name); + bool abort_requirement_satisfied = !require_abort || + btp_glibc_thread_find_exit_frame(thread); + if (btp_debug_parser) + { + printf(" - thread #%d: same_name %s, abort_satisfied %s\n", + thread->number, + same_name ? "true" : "false", + abort_requirement_satisfied ? "true" : "false"); + } + + if (same_name && abort_requirement_satisfied) + { + if (NULL == result) + result = thread; + else + { + /* Second frame with the same function. Failure. */ + return NULL; + } + } + + thread = thread->next; + } + + return result; +} + +struct btp_thread * +btp_backtrace_find_crash_thread(struct btp_backtrace *backtrace) +{ + /* If there is no thread, be silent and report NULL. */ + if (!backtrace->threads) + return NULL; + + /* If there is just one thread, it is simple. */ + if (!backtrace->threads->next) + return backtrace->threads; + + /* If we have a crash frame *and* there is just one thread which has + * this frame on the top, it is also simple. + */ + struct btp_thread *thread; + thread = btp_backtrace_find_crash_thread_from_crash_frame(backtrace, false); + if (thread) + return thread; + + /* There are multiple threads with a frame indistinguishable from + * the crash frame on the top of stack. + * Try to search for known abort functions. + */ + thread = btp_backtrace_find_crash_thread_from_crash_frame(backtrace, true); + + /* We might want to search a thread with known abort function, and + * without the crash frame here. However, it hasn't been needed so + * far. + */ + return thread; /* result or null */ +} + + +void +btp_backtrace_limit_frame_depth(struct btp_backtrace *backtrace, + int depth) +{ + assert(depth > 0); + struct btp_thread *thread = backtrace->threads; + while (thread) + { + btp_thread_remove_frames_below_n(thread, depth); + thread = thread->next; + } +} + +float +btp_backtrace_quality_simple(struct btp_backtrace *backtrace) +{ + int ok_count = 0, all_count = 0; + struct btp_thread *thread = backtrace->threads; + while (thread) + { + btp_thread_quality_counts(thread, &ok_count, &all_count); + thread = thread->next; + } + + if (all_count == 0) + return 0; + + return ok_count / (float)all_count; +} + +float +btp_backtrace_quality_complex(struct btp_backtrace *backtrace) +{ + backtrace = btp_backtrace_dup(backtrace); + + /* Find the crash thread, and then normalize the backtrace. It is + * not possible to find the crash thread after the backtrace has + * been normalized. + */ + struct btp_thread *crash_thread = btp_backtrace_find_crash_thread(backtrace); + btp_normalize_backtrace(backtrace); + + /* Get the quality q1 of the full backtrace. */ + float q1 = btp_backtrace_quality_simple(backtrace); + + if (!crash_thread) + { + btp_backtrace_free(backtrace); + return q1; + } + + /* Get the quality q2 of the crash thread. */ + float q2 = btp_thread_quality(crash_thread); + + /* Get the quality q3 of the frames around the crash. First, + * duplicate the crash thread so we can cut it. Then find an exit + * frame, and remove it and everything above it + * (__run_exit_handlers and such). Then remove all the redundant + * frames (assert calls etc.) Then limit the frame count to 5. + */ + btp_thread_remove_frames_below_n(crash_thread, 5); + float q3 = btp_thread_quality(crash_thread); + + btp_backtrace_free(backtrace); + + /* Compute and return the final backtrace quality q. */ + return 0.25f * q1 + 0.35f * q2 + 0.4f * q3; +} + +char * +btp_backtrace_to_text(struct btp_backtrace *backtrace, bool verbose) +{ + struct btp_strbuf *str = btp_strbuf_new(); + if (verbose) + { + btp_strbuf_append_strf(str, "Thread count: %d\n", + btp_backtrace_get_thread_count(backtrace)); + } + + if (backtrace->crash && verbose) + { + btp_strbuf_append_str(str, "Crash frame: "); + btp_frame_append_to_str(backtrace->crash, str, verbose); + } + + struct btp_thread *thread = backtrace->threads; + while (thread) + { + btp_thread_append_to_str(thread, str, verbose); + thread = thread->next; + } + + return btp_strbuf_free_nobuf(str); +} + +struct btp_frame * +btp_backtrace_get_crash_frame(struct btp_backtrace *backtrace) +{ + backtrace = btp_backtrace_dup(backtrace); + + struct btp_thread *crash_thread = btp_backtrace_find_crash_thread(backtrace); + if (!crash_thread) + { + btp_backtrace_free(backtrace); + return NULL; + } + + btp_normalize_backtrace(backtrace); + struct btp_frame *crash_frame = crash_thread->frames; + crash_frame = btp_frame_dup(crash_frame, false); + btp_backtrace_free(backtrace); + return crash_frame; +} + +char * +btp_backtrace_get_duplication_hash(struct btp_backtrace *backtrace) +{ + backtrace = btp_backtrace_dup(backtrace); + struct btp_thread *crash_thread = btp_backtrace_find_crash_thread(backtrace); + if (crash_thread) + btp_backtrace_remove_threads_except_one(backtrace, crash_thread); + + btp_normalize_backtrace(backtrace); + btp_backtrace_limit_frame_depth(backtrace, 3); + char *hash = btp_backtrace_to_text(backtrace, false); + btp_backtrace_free(backtrace); + return hash; +} + +struct btp_backtrace * +btp_backtrace_parse(char **input, + struct btp_location *location) +{ + char *local_input = *input; + struct btp_backtrace *imbacktrace = btp_backtrace_new(); /* im - intermediate */ + + /* The header is mandatory, but it might contain no frame header, + * in some broken backtraces. In that case, backtrace.crash value + * is kept as NULL. + */ + if (!btp_backtrace_parse_header(&local_input, + &imbacktrace->crash, + location)) + { + btp_backtrace_free(imbacktrace); + return NULL; + } + + struct btp_thread *thread, *prevthread = NULL; + while ((thread = btp_thread_parse(&local_input, location))) + { + if (prevthread) + { + btp_thread_add_sibling(prevthread, thread); + prevthread = thread; + } + else + imbacktrace->threads = prevthread = thread; + } + if (!imbacktrace->threads) + { + btp_backtrace_free(imbacktrace); + return NULL; + } + + *input = local_input; + return imbacktrace; +} + +bool +btp_backtrace_parse_header(char **input, + struct btp_frame **frame, + struct btp_location *location) +{ + int first_thread_line, first_thread_column; + char *first_thread = btp_strstr_location(*input, + "\nThread ", + &first_thread_line, + &first_thread_column); + + /* Skip the newline. */ + if (first_thread) + { + ++first_thread; + first_thread_line += 1; + first_thread_column = 0; + } + + int first_frame_line, first_frame_column; + char *first_frame = btp_strstr_location(*input, + "\n#", + &first_frame_line, + &first_frame_column); + + /* Skip the newline. */ + if (first_frame) + { + ++first_frame; + first_frame_line += 1; + first_frame_column = 0; + } + + if (first_thread) + { + if (first_frame && first_frame < first_thread) + { + /* Common case. The crash frame is present in the input + * before the list of threads begins. + */ + *input = first_frame; + btp_location_add(location, first_frame_line, first_frame_column); + } + else + { + /* Uncommon case (caused by some kernel bug) where the + * frame is missing from the header. The backtrace + * contains just threads. We silently skip the header and + * return true. + */ + *input = first_thread; + btp_location_add(location, + first_thread_line, + first_thread_column); + *frame = NULL; + return true; + } + } + else if (first_frame) + { + /* Degenerate case when the backtrace contains no thread, but + * the frame is there. + */ + *input = first_frame; + btp_location_add(location, first_frame_line, first_frame_column); + } + else + { + /* Degenerate case where the input is empty or completely + * meaningless. Report a failure. + */ + location->message = "No frame and no thread found."; + return false; + } + + /* Parse the frame header. */ + *frame = btp_frame_parse(input, location); + return *frame; +} |