/* 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 #include #include #include 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 strbuf *str = strbuf_new(); if (verbose) { strbuf_append_strf(str, "Thread count: %d\n", btp_backtrace_get_thread_count(backtrace)); } if (backtrace->crash && verbose) { 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 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; }