This patchset adds two functions, sr_distance and sr_threads_compare, which allow you to compare two or multiple threads respectively. The threads can be of any type supported by satyr as long as all threads are of the same type.
The python bindings are not yet updated to accept any thread type -- I'd like to work on [0] first and then modify the python bindings in one go.
Please note that the patches depend on 'source-reorganization' branch sent earlier and won't apply without it. The code is also available at [1].
[0] https://github.com/abrt/satyr/issues/66 [1] https://github.com/abrt/satyr/commits/gh63-agnostic-distance
Martin Milata (6): Fix comment in thread.h Add sr_frame_cmp and sr_frame_cmp_distance Make thread distance type-agnostic distance: normalize levenshtein distance Port tests to type-agnostic distance functions Type-agnostic distance matrices
include/Makefile.am | 1 - include/distance.h | 121 ++++++++++---- include/frame.h | 14 ++ include/metrics.h | 219 -------------------------- include/thread.h | 7 +- lib/Makefile.am | 1 - lib/cluster.c | 2 +- lib/core_frame.c | 4 + lib/core_thread.c | 2 +- lib/distance.c | 406 ++++++++++++++++++++++------------------------- lib/gdb_frame.c | 8 + lib/gdb_thread.c | 2 +- lib/generic_frame.c | 18 +++ lib/generic_frame.h | 3 + lib/generic_thread.h | 4 +- lib/java_frame.c | 2 + lib/java_thread.c | 2 +- lib/koops_frame.c | 2 + lib/koops_stacktrace.c | 2 +- lib/metrics.c | 409 ------------------------------------------------ lib/python_frame.c | 2 + lib/python_stacktrace.c | 2 +- python/py_metrics.c | 14 +- satyr.c | 1 - tests/cluster.at | 3 +- tests/metrics.at | 54 +++---- tests/normalize.at | 1 - 27 files changed, 383 insertions(+), 923 deletions(-) delete mode 100644 include/metrics.h delete mode 100644 lib/metrics.c
Signed-off-by: Martin Milata mmilata@redhat.com --- include/thread.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)
diff --git a/include/thread.h b/include/thread.h index 7694bd3..cb73577 100644 --- a/include/thread.h +++ b/include/thread.h @@ -51,12 +51,15 @@ struct sr_frame * sr_thread_frames(struct sr_thread *thread);
/** - * Compares two threads. Returns 0 on equality. Threads of distinct type are - * always unequal. + * Returns the number of frames in the thread. */ int sr_thread_frame_count(struct sr_thread *thread);
+/** + * Compares two threads. Returns 0 on equality. Threads of distinct type are + * always unequal. + */ int sr_thread_cmp(struct sr_thread *t1, struct sr_thread *t2);
Signed-off-by: Martin Milata mmilata@redhat.com --- include/frame.h | 14 ++++++++++++++ lib/core_frame.c | 4 ++++ lib/core_thread.c | 2 +- lib/gdb_frame.c | 8 ++++++++ lib/gdb_thread.c | 2 +- lib/generic_frame.c | 18 ++++++++++++++++++ lib/generic_frame.h | 3 +++ lib/generic_thread.h | 4 ++-- lib/java_frame.c | 2 ++ lib/java_thread.c | 2 +- lib/koops_frame.c | 2 ++ lib/koops_stacktrace.c | 2 +- lib/python_frame.c | 2 ++ lib/python_stacktrace.c | 2 +- 14 files changed, 60 insertions(+), 7 deletions(-)
diff --git a/include/frame.h b/include/frame.h index bb23419..9eda374 100644 --- a/include/frame.h +++ b/include/frame.h @@ -57,6 +57,20 @@ sr_frame_next(struct sr_frame *frame); void sr_frame_append_to_str(struct sr_frame *frame, struct sr_strbuf *strbuf);
+/** + * Compares two frames. Returns 0 on equality. Frames of distinct type are + * always unequal. + */ +int +sr_frame_cmp(struct sr_frame *t1, struct sr_frame *t2); + +/** + * Compares two frames for the purpose of thread distance computation. Returns + * 0 on equality. Frames of distinct type are always unequal. + */ +int +sr_frame_cmp_distance(struct sr_frame *t1, struct sr_frame *t2); + #ifdef __cplusplus } #endif diff --git a/lib/core_frame.c b/lib/core_frame.c index a2d1ef0..ac3f601 100644 --- a/lib/core_frame.c +++ b/lib/core_frame.c @@ -33,6 +33,8 @@ struct frame_methods core_frame_methods = { .append_to_str = (append_to_str_fn_t) sr_core_frame_append_to_str, .next = (next_frame_fn_t) core_next, + .cmp = (frame_cmp_fn_t) sr_core_frame_cmp, + .cmp_distance = (frame_cmp_fn_t) sr_core_frame_cmp_distance, };
/* Public functions */ @@ -176,6 +178,8 @@ int sr_core_frame_cmp_distance(struct sr_core_frame *frame1, struct sr_core_frame *frame2) { + /* TODO: we should not rely on function name and we definitely should use + * build id */ /* Function name. */ int function_name = sr_strcmp0(frame1->function_name, frame2->function_name); diff --git a/lib/core_thread.c b/lib/core_thread.c index 3ebf1d9..e97f806 100644 --- a/lib/core_thread.c +++ b/lib/core_thread.c @@ -34,7 +34,7 @@ DEFINE_NEXT_FUNC(core_next, struct sr_thread, struct sr_core_thread) struct thread_methods core_thread_methods = { .frames = (frames_fn_t) core_frames, - .cmp = (cmp_fn_t) sr_core_thread_cmp, + .cmp = (thread_cmp_fn_t) sr_core_thread_cmp, .frame_count = (frame_count_fn_t) thread_frame_count, .next = (next_thread_fn_t) core_next, }; diff --git a/lib/gdb_frame.c b/lib/gdb_frame.c index e3b30fb..f9e7f41 100644 --- a/lib/gdb_frame.c +++ b/lib/gdb_frame.c @@ -32,10 +32,18 @@
DEFINE_NEXT_FUNC(gdb_next, struct sr_frame, struct sr_gdb_frame)
+static int +frame_cmp_without_number(struct sr_gdb_frame *frame1, struct sr_gdb_frame *frame2) +{ + return sr_gdb_frame_cmp(frame1, frame2, false); +} + struct frame_methods gdb_frame_methods = { .append_to_str = (append_to_str_fn_t) sr_gdb_frame_append_to_str, .next = (next_frame_fn_t) gdb_next, + .cmp = (frame_cmp_fn_t) frame_cmp_without_number, + .cmp_distance = (frame_cmp_fn_t) sr_gdb_frame_cmp_distance, };
/* Public functions */ diff --git a/lib/gdb_thread.c b/lib/gdb_thread.c index 21acca3..e1af1f2 100644 --- a/lib/gdb_thread.c +++ b/lib/gdb_thread.c @@ -38,7 +38,7 @@ DEFINE_NEXT_FUNC(gdb_next, struct sr_thread, struct sr_gdb_thread) struct thread_methods gdb_thread_methods = { .frames = (frames_fn_t) gdb_frames, - .cmp = (cmp_fn_t) sr_gdb_thread_cmp, + .cmp = (thread_cmp_fn_t) sr_gdb_thread_cmp, .frame_count = (frame_count_fn_t) thread_frame_count, .next = (next_thread_fn_t) gdb_next, }; diff --git a/lib/generic_frame.c b/lib/generic_frame.c index 9041037..83d399e 100644 --- a/lib/generic_frame.c +++ b/lib/generic_frame.c @@ -43,3 +43,21 @@ sr_frame_next(struct sr_frame *frame) { return DISPATCH(dtable, frame->type, next)(frame); } + +int +sr_frame_cmp(struct sr_frame *frame1, struct sr_frame *frame2) +{ + if (frame1->type != frame2->type) + return frame1->type - frame2->type; + + return DISPATCH(dtable, frame1->type, cmp)(frame1, frame2); +} + +int +sr_frame_cmp_distance(struct sr_frame *frame1, struct sr_frame *frame2) +{ + if (frame1->type != frame2->type) + return frame1->type - frame2->type; + + return DISPATCH(dtable, frame1->type, cmp_distance)(frame1, frame2); +} diff --git a/lib/generic_frame.h b/lib/generic_frame.h index 5e28817..138123c 100644 --- a/lib/generic_frame.h +++ b/lib/generic_frame.h @@ -22,11 +22,14 @@
typedef void (*append_to_str_fn_t)(struct sr_frame *, struct sr_strbuf *); typedef struct sr_frame* (*next_frame_fn_t)(struct sr_frame *); +typedef int (*frame_cmp_fn_t)(struct sr_frame *, struct sr_frame *);
struct frame_methods { append_to_str_fn_t append_to_str; next_frame_fn_t next; + frame_cmp_fn_t cmp; + frame_cmp_fn_t cmp_distance; };
extern struct frame_methods core_frame_methods, python_frame_methods, diff --git a/lib/generic_thread.h b/lib/generic_thread.h index e1e5f0a..c53f6fe 100644 --- a/lib/generic_thread.h +++ b/lib/generic_thread.h @@ -21,14 +21,14 @@ #include "thread.h"
typedef struct sr_frame* (*frames_fn_t)(struct sr_thread*); -typedef int (*cmp_fn_t)(struct sr_thread*, struct sr_thread*); +typedef int (*thread_cmp_fn_t)(struct sr_thread*, struct sr_thread*); typedef int (*frame_count_fn_t)(struct sr_thread*); typedef struct sr_thread* (*next_thread_fn_t)(struct sr_thread*);
struct thread_methods { frames_fn_t frames; - cmp_fn_t cmp; + thread_cmp_fn_t cmp; frame_count_fn_t frame_count; next_thread_fn_t next; }; diff --git a/lib/java_frame.c b/lib/java_frame.c index fc8ae29..dfe9f86 100644 --- a/lib/java_frame.c +++ b/lib/java_frame.c @@ -39,6 +39,8 @@ struct frame_methods java_frame_methods = { .append_to_str = (append_to_str_fn_t) sr_java_frame_append_to_str, .next = (next_frame_fn_t) java_next, + .cmp = (frame_cmp_fn_t) sr_java_frame_cmp, + .cmp_distance = (frame_cmp_fn_t) sr_java_frame_cmp_distance, };
/* Public functions */ diff --git a/lib/java_thread.c b/lib/java_thread.c index ef5f73c..f149f76 100644 --- a/lib/java_thread.c +++ b/lib/java_thread.c @@ -38,7 +38,7 @@ DEFINE_NEXT_FUNC(java_next, struct sr_thread, struct sr_java_thread) struct thread_methods java_thread_methods = { .frames = (frames_fn_t) java_frames, - .cmp = (cmp_fn_t) sr_java_thread_cmp, + .cmp = (thread_cmp_fn_t) sr_java_thread_cmp, .frame_count = (frame_count_fn_t) thread_frame_count, .next = (next_thread_fn_t) java_next, }; diff --git a/lib/koops_frame.c b/lib/koops_frame.c index 76f5027..286bc94 100644 --- a/lib/koops_frame.c +++ b/lib/koops_frame.c @@ -36,6 +36,8 @@ struct frame_methods koops_frame_methods = { .append_to_str = (append_to_str_fn_t) sr_koops_frame_append_to_str, .next = (next_frame_fn_t) koops_next, + .cmp = (frame_cmp_fn_t) sr_koops_frame_cmp, + .cmp_distance = (frame_cmp_fn_t) sr_koops_frame_cmp_distance, };
/* Public functions */ diff --git a/lib/koops_stacktrace.c b/lib/koops_stacktrace.c index 16d96a3..f6c4ccb 100644 --- a/lib/koops_stacktrace.c +++ b/lib/koops_stacktrace.c @@ -61,7 +61,7 @@ DEFINE_THREAD_FUNC(koops_frames, struct sr_koops_stacktrace) struct thread_methods koops_thread_methods = { .frames = (frames_fn_t) koops_frames, - .cmp = (cmp_fn_t) NULL, + .cmp = (thread_cmp_fn_t) NULL, .frame_count = (frame_count_fn_t) thread_frame_count, .next = (next_thread_fn_t) thread_no_next_thread, }; diff --git a/lib/python_frame.c b/lib/python_frame.c index 86ecb4e..e3ae238 100644 --- a/lib/python_frame.c +++ b/lib/python_frame.c @@ -35,6 +35,8 @@ struct frame_methods python_frame_methods = { .append_to_str = (append_to_str_fn_t) sr_python_frame_append_to_str, .next = (next_frame_fn_t) python_next, + .cmp = (frame_cmp_fn_t) sr_python_frame_cmp, + .cmp_distance = (frame_cmp_fn_t) sr_python_frame_cmp_distance, };
/* Public functions */ diff --git a/lib/python_stacktrace.c b/lib/python_stacktrace.c index 278d175..fbb0807 100644 --- a/lib/python_stacktrace.c +++ b/lib/python_stacktrace.c @@ -39,7 +39,7 @@ DEFINE_THREAD_FUNC(python_frames, struct sr_python_stacktrace) struct thread_methods python_thread_methods = { .frames = (frames_fn_t) python_frames, - .cmp = (cmp_fn_t) NULL, + .cmp = (thread_cmp_fn_t) NULL, .frame_count = (frame_count_fn_t) thread_frame_count, .next = (next_thread_fn_t) thread_no_next_thread, };
Distance between any pair of threads can now be computed using the single function sr_distance. Related to #63.
Signed-off-by: Martin Milata mmilata@redhat.com --- include/distance.h | 37 +------ lib/distance.c | 313 ++++++++++------------------------------------------- 2 files changed, 61 insertions(+), 289 deletions(-)
diff --git a/include/distance.h b/include/distance.h index 356c715..aab94eb 100644 --- a/include/distance.h +++ b/include/distance.h @@ -31,16 +31,7 @@ extern "C" {
#include <stdbool.h>
-struct sr_gdb_frame; -struct sr_gdb_thread; -struct sr_core_frame; -struct sr_core_thread; -struct sr_java_frame; -struct sr_java_thread; -struct sr_koops_frame; -struct sr_koops_stacktrace; -struct sr_python_frame; -struct sr_python_stacktrace; +struct sr_thread;
enum sr_distance_type { @@ -91,29 +82,9 @@ enum sr_distance_type };
float -sr_distance_gdb(enum sr_distance_type distance_type, - struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2); - -float -sr_distance_core(enum sr_distance_type distance_type, - struct sr_core_thread *thread1, - struct sr_core_thread *thread2); - -float -sr_distance_java(enum sr_distance_type distance_type, - struct sr_java_thread *thread1, - struct sr_java_thread *thread2); - -float -sr_distance_koops(enum sr_distance_type distance_type, - struct sr_koops_stacktrace *stacktrace1, - struct sr_koops_stacktrace *stacktrace2); - -float -sr_distance_python(enum sr_distance_type distance_type, - struct sr_python_stacktrace *stacktrace1, - struct sr_python_stacktrace *stacktrace2); +sr_distance(enum sr_distance_type distance_type, + struct sr_thread *thread1, + struct sr_thread *thread2);
#ifdef __cplusplus } diff --git a/lib/distance.c b/lib/distance.c index ce40aba..197178e 100644 --- a/lib/distance.c +++ b/lib/distance.c @@ -18,37 +18,19 @@ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ #include "distance.h" -#include "gdb/thread.h" -#include "gdb/frame.h" -#include "core/thread.h" -#include "core/frame.h" -#include "java/thread.h" -#include "java/frame.h" -#include "koops/stacktrace.h" -#include "koops/frame.h" -#include "python/stacktrace.h" -#include "python/frame.h" #include "thread.h" +#include "frame.h" #include <stdlib.h> - -typedef int (*frame_cmp_function)(void*, void*); -typedef void* (*frame_next_function)(void*); -typedef void* (*thread_first_frame_function)(void*); - -struct type_specific_functions -{ - frame_cmp_function frame_cmp; - frame_next_function frame_next; - thread_first_frame_function thread_first_frame; -}; +#include <assert.h>
float -distance_jaro_winkler(struct type_specific_functions functions, - void *thread1, - void *thread2) +distance_jaro_winkler(struct sr_thread *thread1, + struct sr_thread *thread2) { - int frame1_count = sr_thread_frame_count((struct sr_thread*) thread1); - int frame2_count = sr_thread_frame_count((struct sr_thread*) thread2); + assert(thread1->type == thread2->type); + + int frame1_count = sr_thread_frame_count(thread1); + int frame2_count = sr_thread_frame_count(thread2);
if (frame1_count == 0 && frame2_count == 0) return 1.0; @@ -61,17 +43,17 @@ distance_jaro_winkler(struct type_specific_functions functions, bool still_prefix = true; float trans_count = 0, match_count = 0;
- void *curr_frame = functions.thread_first_frame(thread1); + struct sr_frame *curr_frame = sr_thread_frames(thread1); for (int i = 1; curr_frame; ++i) { bool match = false; - void *curr_frame2 = functions.thread_first_frame(thread2); + struct sr_frame *curr_frame2 = sr_thread_frames(thread2); for (int j = 1; !match && curr_frame2; ++j) { /* Whether the prefix continues to be the same for both * threads or not. */ - if (i == j && 0 != functions.frame_cmp(curr_frame, curr_frame2)) + if (i == j && 0 != sr_frame_cmp_distance(curr_frame, curr_frame2)) still_prefix = false;
/* Getting a match only if not too far away from each @@ -79,14 +61,14 @@ distance_jaro_winkler(struct type_specific_functions functions, * functions. */ if (abs(i - j) <= max_frame_count / 2 - 1 && - 0 == functions.frame_cmp(curr_frame, curr_frame2)) + 0 == sr_frame_cmp_distance(curr_frame, curr_frame2)) { match = true; if (i != j) ++trans_count; // transposition in place }
- curr_frame2 = functions.frame_next(curr_frame2); + curr_frame2 = sr_frame_next(curr_frame2); }
if (still_prefix) @@ -95,7 +77,7 @@ distance_jaro_winkler(struct type_specific_functions functions, if (match) ++match_count;
- curr_frame = functions.frame_next(curr_frame); + curr_frame = sr_frame_next(curr_frame); }
trans_count /= 2; @@ -120,36 +102,35 @@ distance_jaro_winkler(struct type_specific_functions functions, }
static bool -distance_jaccard_frames_contain(struct type_specific_functions functions, - void *frames, - void *frame) +distance_jaccard_frames_contain(struct sr_frame *haystack, + struct sr_frame *needle) { - while (frames) + while (haystack) { // Checking if functions are the same but not both "??". - if (!functions.frame_cmp(frames, frame)) + if (!sr_frame_cmp_distance(haystack, needle)) return true;
- frames = functions.frame_next(frames); + haystack = sr_frame_next(haystack); }
return false; }
float -distance_jaccard(struct type_specific_functions functions, - void *thread1, - void *thread2) +distance_jaccard(struct sr_thread *thread1, + struct sr_thread *thread2) { + assert(thread1->type == thread2->type); + int intersection_size = 0, set1_size = 0, set2_size = 0;
- for (void *curr_frame = functions.thread_first_frame(thread1); + for (struct sr_frame *curr_frame = sr_thread_frames(thread1); curr_frame; - curr_frame = functions.frame_next(curr_frame)) + curr_frame = sr_frame_next(curr_frame)) { if (distance_jaccard_frames_contain( - functions, - functions.frame_next(curr_frame), + sr_frame_next(curr_frame), curr_frame)) { continue; // not last, skip @@ -158,21 +139,19 @@ distance_jaccard(struct type_specific_functions functions, ++set1_size;
if (distance_jaccard_frames_contain( - functions, - functions.thread_first_frame(thread2), + sr_thread_frames(thread2), curr_frame)) { ++intersection_size; } }
- for (void *curr_frame = functions.thread_first_frame(thread2); + for (struct sr_frame *curr_frame = sr_thread_frames(thread2); curr_frame; - curr_frame = functions.frame_next(curr_frame)) + curr_frame = sr_frame_next(curr_frame)) { if (distance_jaccard_frames_contain( - functions, - functions.frame_next(curr_frame), + sr_frame_next(curr_frame), curr_frame)) { continue; // not last, skip @@ -193,13 +172,14 @@ distance_jaccard(struct type_specific_functions functions, }
float -distance_levenshtein(struct type_specific_functions functions, - void *thread1, - void *thread2, +distance_levenshtein(struct sr_thread *thread1, + struct sr_thread *thread2, bool transposition) { - int m = sr_thread_frame_count((struct sr_thread*) thread1) + 1; - int n = sr_thread_frame_count((struct sr_thread*) thread2) + 1; + assert(thread1->type == thread2->type); + + int m = sr_thread_frame_count(thread1) + 1; + int n = sr_thread_frame_count(thread2) + 1;
// store only two last rows and columns instead of whole 2D array int dist[m + n + 1], dist1[m + n + 1]; @@ -211,13 +191,13 @@ distance_levenshtein(struct type_specific_functions functions, for (int i = 0; i <= n; ++i) dist[m + i] = i;
- void *curr_frame2 = functions.thread_first_frame(thread2); - void *prev_frame = NULL; - void *prev_frame2 = NULL; + struct sr_frame *curr_frame2 = sr_thread_frames(thread2); + struct sr_frame *prev_frame = NULL; + struct sr_frame *prev_frame2 = NULL;
for (int j = 1; curr_frame2; ++j) { - void *curr_frame = functions.thread_first_frame(thread1); + struct sr_frame *curr_frame = sr_thread_frames(thread1); for (int i = 1; curr_frame; ++i) { int l = m + j - i; @@ -230,7 +210,7 @@ distance_levenshtein(struct type_specific_functions functions, /*similar characters have distance equal to the previous one diagonally, "??" functions aren't taken as similar */ - if (0 == functions.frame_cmp(curr_frame, curr_frame2)) + if (0 == sr_frame_cmp_distance(curr_frame, curr_frame2)) cost = 0; else { @@ -249,222 +229,43 @@ distance_levenshtein(struct type_specific_functions functions, taking into account that "??" functions are not similar*/ if (transposition && (i >= 2 && j >= 2 && dist[l] > dist2 + cost && - 0 == functions.frame_cmp(curr_frame, prev_frame2) && - 0 == functions.frame_cmp(prev_frame, curr_frame2))) + 0 == sr_frame_cmp_distance(curr_frame, prev_frame2) && + 0 == sr_frame_cmp_distance(prev_frame, curr_frame2))) { dist[l] = dist2 + cost; }
prev_frame = curr_frame; - curr_frame = functions.frame_next(curr_frame); + curr_frame = sr_frame_next(curr_frame); }
prev_frame2 = curr_frame2; - curr_frame2 = functions.frame_next(curr_frame2); + curr_frame2 = sr_frame_next(curr_frame2); }
return dist[n]; }
-static float -distance(enum sr_distance_type distance_type, - struct type_specific_functions functions, - void *thread1, - void *thread2) +float +sr_distance(enum sr_distance_type distance_type, + struct sr_thread *thread1, + struct sr_thread *thread2) { + /* Different thread types are always unequal. */ + if (thread1->type != thread2->type) + return 1.0f; + switch (distance_type) { case SR_DISTANCE_JARO_WINKLER: - return distance_jaro_winkler(functions, thread1, thread2); + return distance_jaro_winkler(thread1, thread2); case SR_DISTANCE_JACCARD: - return distance_jaccard(functions, thread1, thread2); + return distance_jaccard(thread1, thread2); case SR_DISTANCE_LEVENSHTEIN: - return distance_levenshtein(functions, thread1, thread2, false); + return distance_levenshtein(thread1, thread2, false); case SR_DISTANCE_DAMERAU_LEVENSHTEIN: - return distance_levenshtein(functions, thread1, thread2, true); + return distance_levenshtein(thread1, thread2, true); default: return 1.0f; } } - -static int -frame_cmp_gdb(void *frame1, void *frame2) -{ - return sr_gdb_frame_cmp_distance((struct sr_gdb_frame*)frame1, - (struct sr_gdb_frame*)frame2); -} - -static void * -frame_next_gdb(void *frame) -{ - return ((struct sr_gdb_frame*)frame)->next; -} - -static void * -thread_first_frame_gdb(void *thread) -{ - return ((struct sr_gdb_thread*)thread)->frames; -} - -struct type_specific_functions gdb_specific_functions = { - frame_cmp_gdb, - frame_next_gdb, - thread_first_frame_gdb, -}; - -float -sr_distance_gdb(enum sr_distance_type distance_type, - struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2) -{ - return distance(distance_type, - gdb_specific_functions, - thread1, - thread2); -} - -static int -frame_cmp_core(void *frame1, void *frame2) -{ - return sr_core_frame_cmp_distance((struct sr_core_frame*)frame1, - (struct sr_core_frame*)frame2); -} - -static void * -frame_next_core(void *frame) -{ - return ((struct sr_core_frame*)frame)->next; -} - -static void * -thread_first_frame_core(void *thread) -{ - return ((struct sr_core_thread*)thread)->frames; -} - -struct type_specific_functions core_specific_functions = { - frame_cmp_core, - frame_next_core, - thread_first_frame_core, -}; - -float -sr_distance_core(enum sr_distance_type distance_type, - struct sr_core_thread *thread1, - struct sr_core_thread *thread2) -{ - return distance(distance_type, - core_specific_functions, - thread1, - thread2); -} - -static int -frame_cmp_java(void *frame1, void *frame2) -{ - return sr_java_frame_cmp_distance((struct sr_java_frame*)frame1, - (struct sr_java_frame*)frame2); -} - -static void * -frame_next_java(void *frame) -{ - return ((struct sr_java_frame*)frame)->next; -} - -static void * -thread_first_frame_java(void *thread) -{ - return ((struct sr_java_thread*)thread)->frames; -} - -struct type_specific_functions java_specific_functions = { - frame_cmp_java, - frame_next_java, - thread_first_frame_java, -}; - -float -sr_distance_java(enum sr_distance_type distance_type, - struct sr_java_thread *thread1, - struct sr_java_thread *thread2) -{ - return distance(distance_type, - java_specific_functions, - thread1, - thread2); -} - -static int -frame_cmp_koops(void *frame1, void *frame2) -{ - return sr_koops_frame_cmp_distance((struct sr_koops_frame*)frame1, - (struct sr_koops_frame*)frame2); -} - -static void * -frame_next_koops(void *frame) -{ - return ((struct sr_koops_frame*)frame)->next; -} - -static void * -thread_first_frame_koops(void *stacktrace) -{ - return ((struct sr_koops_stacktrace*)stacktrace)->frames; -} - -struct type_specific_functions koops_specific_functions = { - frame_cmp_koops, - frame_next_koops, - thread_first_frame_koops, -}; - -float -sr_distance_koops(enum sr_distance_type distance_type, - struct sr_koops_stacktrace *stacktrace1, - struct sr_koops_stacktrace *stacktrace2) -{ - return distance(distance_type, - koops_specific_functions, - stacktrace1, - stacktrace2); -} - - -static int -frame_cmp_python(void *frame1, void *frame2) -{ - return sr_python_frame_cmp_distance((struct sr_python_frame*)frame1, - (struct sr_python_frame*)frame2); -} - -static void * -frame_next_python(void *frame) -{ - return ((struct sr_python_frame*)frame)->next; -} - -static void * -thread_first_frame_python(void *stacktrace) -{ - return ((struct sr_python_stacktrace*)stacktrace)->frames; -} - -struct type_specific_functions python_specific_functions = { - frame_cmp_python, - frame_next_python, - thread_first_frame_python, -}; - -float -sr_distance_python(enum sr_distance_type distance_type, - struct sr_python_stacktrace *stacktrace1, - struct sr_python_stacktrace *stacktrace2) -{ - return distance(distance_type, - python_specific_functions, - stacktrace1, - stacktrace2); -} -
The result is normalized between 0.0 and 1.0, as is described in the comment.
Signed-off-by: Martin Milata mmilata@redhat.com --- lib/distance.c | 17 ++++++++++++++--- 1 file changed, 14 insertions(+), 3 deletions(-)
diff --git a/lib/distance.c b/lib/distance.c index 197178e..222572e 100644 --- a/lib/distance.c +++ b/lib/distance.c @@ -178,8 +178,19 @@ distance_levenshtein(struct sr_thread *thread1, { assert(thread1->type == thread2->type);
- int m = sr_thread_frame_count(thread1) + 1; - int n = sr_thread_frame_count(thread2) + 1; + int frame_count1 = sr_thread_frame_count(thread1); + int frame_count2 = sr_thread_frame_count(thread2); + + int max_frame_count = frame_count2; + if (max_frame_count < frame_count1) + max_frame_count = frame_count1; + + /* Avoid division by zero in case we get two empty threads */ + if (max_frame_count == 0) + return 0.0; + + int m = frame_count1 + 1; + int n = frame_count2 + 1;
// store only two last rows and columns instead of whole 2D array int dist[m + n + 1], dist1[m + n + 1]; @@ -243,7 +254,7 @@ distance_levenshtein(struct sr_thread *thread1, curr_frame2 = sr_frame_next(curr_frame2); }
- return dist[n]; + return (float)dist[n] / max_frame_count; }
float
Signed-off-by: Martin Milata mmilata@redhat.com --- tests/metrics.at | 51 ++++++++++++++++++++++++++------------------------- 1 file changed, 26 insertions(+), 25 deletions(-)
diff --git a/tests/metrics.at b/tests/metrics.at index 5656ef0..7f56fce 100644 --- a/tests/metrics.at +++ b/tests/metrics.at @@ -9,6 +9,7 @@ m4_define([UTILS], #include <assert.h> #include "metrics.h" #include "normalize.h" +#include "distance.h"
static struct sr_gdb_thread * create_thread(int count, ...) @@ -55,9 +56,9 @@ main() struct sr_gdb_thread *thread1 = create_thread(0); struct sr_gdb_thread *thread2 = create_thread(3, "??", "ds", "main"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(is_dist_equal(0.0, sr_gdb_thread_jarowinkler_distance(thread1, thread2))); - assert(is_dist_equal(1.0, sr_gdb_thread_jaccard_distance(thread1, thread2))); - assert(3 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(0.0, sr_distance(SR_DISTANCE_JARO_WINKLER, thread1, thread2))); + assert(is_dist_equal(1.0, sr_distance(SR_DISTANCE_JACCARD, thread1, thread2))); + assert(is_dist_equal(1.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -72,9 +73,9 @@ main() struct sr_gdb_thread *thread1 = create_thread(0); struct sr_gdb_thread *thread2 = create_thread(0); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(is_dist_equal(1.0, sr_gdb_thread_jarowinkler_distance(thread1, thread2))); - assert(is_dist_equal(0.0, sr_gdb_thread_jaccard_distance(thread1, thread2))); - assert(0 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(1.0, sr_distance(SR_DISTANCE_JARO_WINKLER, thread1, thread2))); + assert(is_dist_equal(0.0, sr_distance(SR_DISTANCE_JACCARD, thread1, thread2))); + assert(is_dist_equal(0.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -89,9 +90,9 @@ main() struct sr_gdb_thread *thread1 = create_thread(2, "??", "sd"); struct sr_gdb_thread *thread2 = create_thread(3, "??", "ds", "main"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(is_dist_equal(0.0, sr_gdb_thread_jarowinkler_distance(thread1, thread2))); - assert(is_dist_equal(1.0, sr_gdb_thread_jaccard_distance(thread1, thread2))); - assert(3 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(0.0, sr_distance(SR_DISTANCE_JARO_WINKLER, thread1, thread2))); + assert(is_dist_equal(1.0, sr_distance(SR_DISTANCE_JACCARD, thread1, thread2))); + assert(is_dist_equal(1.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -106,9 +107,9 @@ main() struct sr_gdb_thread *thread1 = create_thread(1, "??"); struct sr_gdb_thread *thread2 = create_thread(3, "??", "ds", "main"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(is_dist_equal(0.0, sr_gdb_thread_jarowinkler_distance(thread1, thread2))); - assert(is_dist_equal(1.0, sr_gdb_thread_jaccard_distance(thread1, thread2))); - assert(3 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(0.0, sr_distance(SR_DISTANCE_JARO_WINKLER, thread1, thread2))); + assert(is_dist_equal(1.0, sr_distance(SR_DISTANCE_JACCARD, thread1, thread2))); + assert(is_dist_equal(1.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -123,7 +124,7 @@ main() struct sr_gdb_thread *thread1 = create_thread(3, "??", "ds", "main"); struct sr_gdb_thread *thread2 = create_thread(3, "??", "ds", "main"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(0 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(0.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -138,7 +139,7 @@ main() struct sr_gdb_thread *thread1 = create_thread(4, "dg", "??", "ds", "main"); struct sr_gdb_thread *thread2 = create_thread(4, "dg", "??", "ds", "main"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(0 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(0.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -153,7 +154,7 @@ main() struct sr_gdb_thread *thread1 = create_thread(3, "dg", "??", "ds"); struct sr_gdb_thread *thread2 = create_thread(4, "dg", "??", "ds", "main"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(1 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(1/4.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -168,7 +169,7 @@ main() struct sr_gdb_thread *thread1 = create_thread(2, "dg", "??"); struct sr_gdb_thread *thread2 = create_thread(3, "dg", "??", "main"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(2 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(2/3.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -183,7 +184,7 @@ main() struct sr_gdb_thread *thread1 = create_thread(3, "dg", "??", "??"); struct sr_gdb_thread *thread2 = create_thread(4, "dg", "??", "??", "main"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(3 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(3/4.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -198,7 +199,7 @@ main() struct sr_gdb_thread *thread1 = create_thread(3, "??", "??", "main"); struct sr_gdb_thread *thread2 = create_thread(2, "??", "??"); sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - assert(3 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(1.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -216,7 +217,7 @@ main()
sr_normalize_gdb_paired_unknown_function_names(thread1, thread2);
- assert(2 == sr_gdb_thread_levenshtein_distance(thread1, thread2, true)); + assert(is_dist_equal(2/5.0, sr_distance(SR_DISTANCE_DAMERAU_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -234,7 +235,7 @@ main()
sr_normalize_gdb_paired_unknown_function_names(thread1, thread2);
- assert(2 == sr_gdb_thread_levenshtein_distance(thread1, thread2, true)); + assert(is_dist_equal(2/4.0, sr_distance(SR_DISTANCE_DAMERAU_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -249,7 +250,7 @@ main() struct sr_gdb_thread *thread1 = create_thread(4, "a", "b", "c", "d"); struct sr_gdb_thread *thread2 = create_thread(4, "b", "a", "d", "c");
- assert(2 == sr_gdb_thread_levenshtein_distance(thread1, thread2, true)); + assert(is_dist_equal(2/4.0, sr_distance(SR_DISTANCE_DAMERAU_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -264,7 +265,7 @@ main() struct sr_gdb_thread *thread1 = create_thread(4, "a", "b", "c", "d"); struct sr_gdb_thread *thread2 = create_thread(4, "b", "a", "d", "c");
- assert(3 == sr_gdb_thread_levenshtein_distance(thread1, thread2, false)); + assert(is_dist_equal(3/4.0, sr_distance(SR_DISTANCE_LEVENSHTEIN, thread1, thread2))); return 0; } ]) @@ -282,7 +283,7 @@ main()
sr_normalize_gdb_paired_unknown_function_names(thread1, thread2);
- assert(is_dist_equal(0.0, sr_gdb_thread_jaccard_distance(thread1, thread2))); + assert(is_dist_equal(0.0, sr_distance(SR_DISTANCE_JACCARD, thread1, thread2))); return 0; } ]) @@ -298,7 +299,7 @@ main()
struct sr_gdb_thread *thread2 = create_thread(2, "sad", "agd");
- assert(is_dist_equal(2/3.0, sr_gdb_thread_jaccard_distance(thread1, thread2))); + assert(is_dist_equal(2/3.0, sr_distance(SR_DISTANCE_JACCARD, thread1, thread2))); return 0; } ]) @@ -314,7 +315,7 @@ main()
struct sr_gdb_thread *thread2 = create_thread(4, "sad", "sad", "sad", "gad");
- assert(is_dist_equal(3/5.0, sr_gdb_thread_jaccard_distance(thread1, thread2))); + assert(is_dist_equal(3/5.0, sr_distance(SR_DISTANCE_JACCARD, thread1, thread2))); return 0; } ])
- the code that creates distance matrices was modified to accept array of sr_thread pointers - metrics.c was deleted and the distance matrix code was moved to distance.c (metrics.c contained different implementation of distance functions, probably left over after their rewrite in distance.c) - tests adjusted - python bindings adjusted to compile, the satyr.Distances constructor still only accepts GDB threads though
Related to #63 (does not close it, the python bindings still need more work).
Signed-off-by: Martin Milata mmilata@redhat.com --- include/Makefile.am | 1 - include/distance.h | 94 ++++++++++++ include/metrics.h | 219 ---------------------------- lib/Makefile.am | 1 - lib/cluster.c | 2 +- lib/distance.c | 160 ++++++++++++++++++++ lib/metrics.c | 409 ---------------------------------------------------- python/py_metrics.c | 14 +- satyr.c | 1 - tests/cluster.at | 3 +- tests/metrics.at | 3 +- tests/normalize.at | 1 - 12 files changed, 264 insertions(+), 644 deletions(-) delete mode 100644 include/metrics.h delete mode 100644 lib/metrics.c
diff --git a/include/Makefile.am b/include/Makefile.am index 89e0201..f72ec66 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -5,7 +5,6 @@ mainheaders_HEADERS = \ distance.h \ json.h \ location.h \ - metrics.h \ normalize.h \ operating_system.h \ report.h \ diff --git a/include/distance.h b/include/distance.h index aab94eb..53be6d7 100644 --- a/include/distance.h +++ b/include/distance.h @@ -86,6 +86,100 @@ sr_distance(enum sr_distance_type distance_type, struct sr_thread *thread1, struct sr_thread *thread2);
+/** + * @brief A distance matrix of stack trace threads. + * + * The distances are stored in a m-by-n two-dimensional array, where + * only entries (i, j) where i < j are actually stored. + */ +struct sr_distances +{ + int m; + int n; + float *distances; +}; + +/** + * Creates and initializes a new distances structure. + * @param m + * Number of rows. + * @param n + * Number of columns. + * @returns + * It never returns NULL. The returned pointer must be released by + * calling the function sr_distances_free(). + */ +struct sr_distances * +sr_distances_new(int m, int n); + +/** + * Creates a duplicate of the distances structure. + * @param distances + * It must be non-NULL pointer. The structure is not modified by calling + * this function. + * @returns + * This function never returns NULL. + */ +struct sr_distances * +sr_distances_dup(struct sr_distances *distances); + +/** + * Releases the memory held by the distances structure. + * @param distances + * If the distances is NULL, no operation is performed. + */ +void +sr_distances_free(struct sr_distances *distances); + +/** + * Gets the entry (i, j) from the distance matrix. + * @param distances + * It must be non-NULL pointer. + * @param i + * Row in the matrix. + * @param j + * Column in the matrix. + * @returns + * For entries (i, i) zero distance is returned and values returned for + * entries (i, j) and (j, i) are the same. + */ +float +sr_distances_get_distance(struct sr_distances *distances, int i, int j); + +/** + * Sets the entry (i, j) from the distance matrix. + * @param distances + * It must be non-NULL pointer. + * @param i + * Row in the matrix. + * @param j + * Column in the matrix. + * @param d + * Distance. + */ +void +sr_distances_set_distance(struct sr_distances *distances, + int i, + int j, + float d); + +/** + * Creates a distances structure by comparing threads. + * @param threads + * Array of threads. They are not modified by calling this function. + * @param m + * Compare first m threads from the array with other threads. + * @param n + * Number of threads in the passed array. + * @param dist_func + * Distance function which will be used to compare the threads. It's assumed to + * be symmetric and return zero distance for equal threads. + * @returns + * This function never returns NULL. + */ +struct sr_distances * +sr_threads_compare(struct sr_thread **threads, int m, int n, + enum sr_distance_type dist_type); #ifdef __cplusplus } #endif diff --git a/include/metrics.h b/include/metrics.h deleted file mode 100644 index 9deddf4..0000000 --- a/include/metrics.h +++ /dev/null @@ -1,219 +0,0 @@ -/* - metrics.h - - 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. -*/ -#ifndef SATYR_METRICS_H -#define SATYR_METRICS_H - -/** - * @file - * @brief Distance between stack trace threads. - */ - -#ifdef __cplusplus -extern "C" { -#endif - -#include <stdbool.h> - -struct sr_gdb_frame; -struct sr_gdb_thread; - -/* Jaro-Winkler distance: - * - * Gets number of matching function names(match_count) from both - * threads and number of transpositions in place(trans_count) if the - * transpositioned function names are not farther away than - * frame_count/2 - 1. Then computes the Jaro-Winkler distance - * according to the formula. NOTE: The Jaro-Winkler distance is not a - * metric distance as it does not satisfy the triangle inequality. - * Returns a number between 0 and 1: 0 = no similarity, 1 = similar - * threads - */ -float -sr_gdb_thread_jarowinkler_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2); - - -/* Jaccard distance: - * - * Gives a number representing the difference of the size of the - * intersection and union divided by the size of the union of two - * threads. Function names positions in the thread are not taken into - * account. Returns a number between 0 and 1: 0 = similar threads, 1 - * = no similarity - */ -float -sr_gdb_thread_jaccard_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2); - - -/* Levenshtein distance: - * - * Computes the distance of two threads creating a matrix of distances - * between all the frames in each thread. Returns a number - * representing how many function names need to be different in one - * thread to match all the function names in second thread at each - * respective positions or how many function names need to be - * different/transpositioned to have a match if the transposition - * argument is enabled. NOTE: With transpositions enabled the - * triangle inequality does not hold. The distance is always between - * 0 and n, where n is the frame count of longer thread 0 = similar - * threads, n = no similar function names - */ -int -sr_gdb_thread_levenshtein_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - bool transposition); - -/* Levenshtein distance returned with transpositions enabled and - * returned in interval [0, 1]. - */ -float -sr_gdb_thread_levenshtein_distance_f(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2); - -typedef int (*sr_gdb_frame_cmp_type)(struct sr_gdb_frame*, - struct sr_gdb_frame*); - -/* Following three functions are equivalent to the three above except - * that they take frame comparison function as an argument argument - */ -float -sr_gdb_thread_jarowinkler_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - sr_gdb_frame_cmp_type compare_func); - -float -sr_gdb_thread_jaccard_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - sr_gdb_frame_cmp_type compare_func); - -int -sr_gdb_thread_levenshtein_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - bool transposition, - sr_gdb_frame_cmp_type compare_func); - -/** - * @brief A distance matrix of stack trace threads. - * - * The distances are stored in a m-by-n two-dimensional array, where - * only entries (i, j) where i < j are actually stored. - */ -struct sr_distances -{ - int m; - int n; - float *distances; -}; - -/** - * Creates and initializes a new distances structure. - * @param m - * Number of rows. - * @param n - * Number of columns. - * @returns - * It never returns NULL. The returned pointer must be released by - * calling the function sr_distances_free(). - */ -struct sr_distances * -sr_distances_new(int m, int n); - -/** - * Creates a duplicate of the distances structure. - * @param distances - * It must be non-NULL pointer. The structure is not modified by calling - * this function. - * @returns - * This function never returns NULL. - */ -struct sr_distances * -sr_distances_dup(struct sr_distances *distances); - -/** - * Releases the memory held by the distances structure. - * @param distances - * If the distances is NULL, no operation is performed. - */ -void -sr_distances_free(struct sr_distances *distances); - -/** - * Gets the entry (i, j) from the distance matrix. - * @param distances - * It must be non-NULL pointer. - * @param i - * Row in the matrix. - * @param j - * Column in the matrix. - * @returns - * For entries (i, i) zero distance is returned and values returned for - * entries (i, j) and (j, i) are the same. - */ -float -sr_distances_get_distance(struct sr_distances *distances, int i, int j); - -/** - * Sets the entry (i, j) from the distance matrix. - * @param distances - * It must be non-NULL pointer. - * @param i - * Row in the matrix. - * @param j - * Column in the matrix. - * @param d - * Distance. - */ -void -sr_distances_set_distance(struct sr_distances *distances, - int i, - int j, - float d); - -/** - * A function which compares two threads. - */ -typedef float (*sr_dist_thread_type)(struct sr_gdb_thread *, - struct sr_gdb_thread *); - -/** - * Creates a distances structure by comparing threads. - * @param threads - * Array of threads. They are not modified by calling this function. - * @param m - * Compare first m threads from the array with other threads. - * @param n - * Number of threads in the passed array. - * @param dist_func - * Distance function which will be used to compare the threads. It's assumed to - * be symmetric and return zero distance for equal threads. - * @returns - * This function never returns NULL. - */ -struct sr_distances * -sr_gdb_threads_compare(struct sr_gdb_thread **threads, - int m, int n, - sr_dist_thread_type dist_func); - -#ifdef __cplusplus -} -#endif - -#endif diff --git a/lib/Makefile.am b/lib/Makefile.am index 277f53d..9e1db0c 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -38,7 +38,6 @@ libsatyr_la_SOURCES = \ koops_frame.c \ koops_stacktrace.c \ location.c \ - metrics.c \ normalize.c \ operating_system.c \ python_frame.c \ diff --git a/lib/cluster.c b/lib/cluster.c index 75c9f61..92d5304 100644 --- a/lib/cluster.c +++ b/lib/cluster.c @@ -19,7 +19,7 @@ */
#include "cluster.h" -#include "metrics.h" +#include "distance.h" #include "utils.h" #include <stdlib.h> #include <string.h> diff --git a/lib/distance.c b/lib/distance.c index 222572e..0022655 100644 --- a/lib/distance.c +++ b/lib/distance.c @@ -20,8 +20,12 @@ #include "distance.h" #include "thread.h" #include "frame.h" +#include "normalize.h" +#include "utils.h" +#include "gdb/thread.h" #include <stdlib.h> #include <assert.h> +#include <string.h>
float distance_jaro_winkler(struct sr_thread *thread1, @@ -280,3 +284,159 @@ sr_distance(enum sr_distance_type distance_type, return 1.0f; } } + +static int +get_distance_position(const struct sr_distances *distances, int i, int j) +{ + /* The array holds only matrix entries (i, j) where i < j, + * locate the position in the array. */ + assert(i < j && i >= 0 && i < distances->m && j < distances->n); + + int h = distances->n, l = distances->n - i; + + return ((h * h - h) - (l * l - l)) / 2 + j - 1; +} + +struct sr_distances * +sr_distances_new(int m, int n) +{ + struct sr_distances *distances = sr_malloc(sizeof(struct sr_distances)); + + /* The number of rows has to be smaller than columns. */ + if (m >= n) + m = n - 1; + + assert(m > 0 && n > 1 && m < n); + + distances->m = m; + distances->n = n; + distances->distances = sr_malloc(sizeof(*distances->distances) * + (get_distance_position(distances, m - 1, n - 1) + 1)); + + return distances; +} + +struct sr_distances * +sr_distances_dup(struct sr_distances *distances) +{ + struct sr_distances *dup_distances; + + dup_distances = sr_distances_new(distances->m, distances->n); + memcpy(dup_distances->distances, distances->distances, + sizeof(*distances->distances) * + (get_distance_position(distances, distances->m - 1, distances->n - 1) + 1)); + + return dup_distances; +} + +void +sr_distances_free(struct sr_distances *distances) +{ + if (!distances) + return; + + free(distances->distances); + free(distances); +} + +float +sr_distances_get_distance(struct sr_distances *distances, int i, int j) +{ + if (i == j) + return 0.0; + + if (i > j) + { + int x; + x = j, j = i, i = x; + } + + return distances->distances[get_distance_position(distances, i, j)]; +} + +void +sr_distances_set_distance(struct sr_distances *distances, + int i, + int j, + float d) +{ + if (i == j) + return; + + if (i > j) + { + int x; + x = j, j = i, i = x; + } + + distances->distances[get_distance_position(distances, i, j)] = d; +} + +struct sr_distances * +sr_threads_compare(struct sr_thread **threads, + int m, + int n, + enum sr_distance_type dist_type) +{ + struct sr_distances *distances; + int i, j; + float dist; + + distances = sr_distances_new(m, n); + + if (n <= 0) + return distances; + + /* Check that all threads are of the same type */ + enum sr_report_type type, prev_type = threads[0]->type; + for (i = 0; i < n; i++) + { + type = threads[i]->type; + assert(prev_type == type); + prev_type = type; + } + + for (i = 0; i < m; i++) + { + for (j = i + 1; j < n; j++) + { + /* XXX: GDB crashes have a special normalization step for + * clustering. If there's something similar for other types, we can + * generalize it -- meanwhile there's a separate case for GDB here + */ + if (type == SR_REPORT_GDB) + { + struct sr_gdb_thread *thread1 = (struct sr_gdb_thread*)threads[i], + *thread2 = (struct sr_gdb_thread*)threads[j]; + int ok = 0, all = 0; + + sr_gdb_thread_quality_counts(thread1, &ok, &all); + sr_gdb_thread_quality_counts(thread2, &ok, &all); + + if (ok != all) + { + /* There are some unknown function names, try to pair them, but + * the threads need to be copied first. */ + thread1 = sr_gdb_thread_dup(thread1, false); + thread2 = sr_gdb_thread_dup(thread2, false); + sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); + } + + dist = sr_distance(dist_type, (struct sr_thread*)thread1, + (struct sr_thread*)thread2); + + if (ok != all) + { + sr_gdb_thread_free(thread1); + sr_gdb_thread_free(thread2); + } + } + else + dist = sr_distance(dist_type, threads[i], threads[j]); + + distances->distances[get_distance_position(distances, i, j)] = dist; + } + } + + return distances; +} diff --git a/lib/metrics.c b/lib/metrics.c deleted file mode 100644 index 40fa87a..0000000 --- a/lib/metrics.c +++ /dev/null @@ -1,409 +0,0 @@ -/* - metrics.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 "gdb/thread.h" -#include "gdb/frame.h" -#include "utils.h" -#include "metrics.h" -#include "normalize.h" -#include "thread.h" -#include <stdio.h> -#include <limits.h> -#include <string.h> -#include <assert.h> - -float -sr_gdb_thread_jarowinkler_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - sr_gdb_frame_cmp_type compare_func) -{ - int frame1_count = sr_thread_frame_count((struct sr_thread*) thread1); - int frame2_count = sr_thread_frame_count((struct sr_thread*) thread2); - - if (frame1_count == 0 && frame2_count == 0) - { - return 1.0; - } - - int max_frame_count = (frame2_count > frame1_count ? frame2_count : frame1_count); - int i = 0, j, prefix_len = 0; - bool match, still_prefix = true; - float k, trans_count = 0, match_count = 0, dist_jaro, dist; - - - struct sr_gdb_frame *curr_frame = thread1->frames; - for (i = 1; curr_frame; i++) - { - match = false; - struct sr_gdb_frame *curr_frame2 = thread2->frames; - for (j = 1; !match && curr_frame2; j++) - { - /*whether the prefix continues to be the same for both threads or not*/ - if (i == j && 0 != compare_func(curr_frame, curr_frame2)) - still_prefix = false; - - /*getting a match only if not too far away from each other - and if functions aren't both unpaired unknown functions */ - - if (abs(i - j) <= max_frame_count / 2 - 1 && - 0 == compare_func(curr_frame, curr_frame2)) - { - match = true; - if(i != j)trans_count++; // transposition in place - } - curr_frame2 = curr_frame2->next; - } - - if (still_prefix) - prefix_len++; - - if (match) - match_count++; - - curr_frame = curr_frame->next; - } - - trans_count = trans_count / 2; - - if (prefix_len > 4) - prefix_len = 4; - - if (match_count == 0)return 0; // so as not to divide by 0 - - dist_jaro = (match_count / (float)frame1_count + - match_count / (float)frame2_count + - (match_count - trans_count) / match_count) / 3; - - k = 0.2; /* how much weight we give to having common prefixes - * (always k < 0.25) */ - - dist = dist_jaro + (float)prefix_len * k * (1 - dist_jaro); - - return dist; -} - -static bool -frames_contain(struct sr_gdb_frame *frames, - struct sr_gdb_frame *frame, - sr_gdb_frame_cmp_type compare_func) -{ - while (frames) - { - // checking if functions are the same but not both "??" - if (!compare_func(frames, frame)) - return true; - - frames = frames->next; - } - - return false; -} - -float -sr_gdb_thread_jaccard_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - sr_gdb_frame_cmp_type compare_func) -{ - int union_size, intersection_size = 0, set1_size = 0, set2_size = 0; - float j_distance; - struct sr_gdb_frame *curr_frame; - - for (curr_frame = thread1->frames; curr_frame; curr_frame = curr_frame->next) - { - if (frames_contain(curr_frame->next, curr_frame, compare_func)) - continue; // not last, skip - - set1_size++; - - if (frames_contain(thread2->frames, curr_frame, compare_func)) - intersection_size++; - } - - for (curr_frame = thread2->frames; curr_frame; curr_frame = curr_frame->next) - { - if (frames_contain(curr_frame->next, curr_frame, compare_func)) - continue; // not last, skip - - set2_size++; - } - - union_size = set1_size + set2_size - intersection_size; - if (!union_size) - return 0.0; - - j_distance = 1.0 - intersection_size / (float)union_size; - if (j_distance < 0.0) - j_distance = 0.0; - - return j_distance; -} - - -int -sr_gdb_thread_levenshtein_distance_custom(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - bool transposition, - sr_gdb_frame_cmp_type compare_func) -{ - int m = sr_thread_frame_count((struct sr_thread*) thread1) + 1; - int n = sr_thread_frame_count((struct sr_thread*) thread2) + 1; - - // store only two last rows and columns instead of whole 2D array - int dist[m + n + 1], dist1[m + n + 1], dist2; - - int i, j, l, cost = 0; - - // first row and column having distance equal to their position - for (i = m; i > 0; i--) - dist[m - i] = i; - - for (; i <= n; i++) - dist[m + i] = i; - - struct sr_gdb_frame *curr_frame2 = thread2->frames; - struct sr_gdb_frame *prev_frame = NULL; - struct sr_gdb_frame *prev_frame2 = NULL; - - for (j = 1; curr_frame2; j++) - { - struct sr_gdb_frame *curr_frame = thread1->frames; - for (i = 1; curr_frame; i++) - { - l = m + j - i; - - dist2 = dist1[l]; - dist1[l] = dist[l]; - - /*similar characters have distance equal to the previous one diagonally, - "??" functions aren't taken as similar */ - if (0 == compare_func(curr_frame, curr_frame2)) - cost = 0; - // different ones takes the lowest value of all previous distances - else - { - cost = 1; - dist[l] += 1; - if (dist[l] > dist[l - 1] + 1) - dist[l] = dist[l - 1] + 1; - if (dist[l] > dist[l + 1] + 1) - dist[l] = dist[l + 1] + 1; - } - - /*checking for transposition of two characters in both ways - taking into account that "??" functions are not similar*/ - if (transposition && - (i >= 2 && j >= 2 && dist[l] > dist2 + cost && - 0 == compare_func(curr_frame, prev_frame2) && - 0 == compare_func(prev_frame, curr_frame2))) - { - dist[l] = dist2 + cost; - } - - prev_frame = curr_frame; - curr_frame = curr_frame->next; - } - - prev_frame2 = curr_frame2; - curr_frame2 = curr_frame2->next; - } - - return dist[n]; -} - -float -sr_gdb_thread_jarowinkler_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2) -{ - return sr_gdb_thread_jarowinkler_distance_custom(thread1, - thread2, - sr_gdb_frame_cmp_distance); -} - -float -sr_gdb_thread_jaccard_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2) -{ - return sr_gdb_thread_jaccard_distance_custom(thread1, - thread2, - sr_gdb_frame_cmp_distance); -} - -int -sr_gdb_thread_levenshtein_distance(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2, - bool transposition) -{ - return sr_gdb_thread_levenshtein_distance_custom(thread1, - thread2, - transposition, - sr_gdb_frame_cmp_distance); -} - -float -sr_gdb_thread_levenshtein_distance_f(struct sr_gdb_thread *thread1, - struct sr_gdb_thread *thread2) -{ - int frame_count1, frame_count2, max_frame_count; - - frame_count1 = sr_thread_frame_count((struct sr_thread*) thread1); - frame_count2 = sr_thread_frame_count((struct sr_thread*) thread2); - max_frame_count = frame_count1 > frame_count2 ? frame_count1 : frame_count2; - - if (!max_frame_count) - return 1.0; - - return (float)sr_gdb_thread_levenshtein_distance_custom(thread1, - thread2, - true, - sr_gdb_frame_cmp_distance) / max_frame_count; -} - -static int -get_distance_position(const struct sr_distances *distances, int i, int j) -{ - /* The array holds only matrix entries (i, j) where i < j, - * locate the position in the array. */ - assert(i < j && i >= 0 && i < distances->m && j < distances->n); - - int h = distances->n, l = distances->n - i; - - return ((h * h - h) - (l * l - l)) / 2 + j - 1; -} - -struct sr_distances * -sr_distances_new(int m, int n) -{ - struct sr_distances *distances = sr_malloc(sizeof(struct sr_distances)); - - /* The number of rows has to be smaller than columns. */ - if (m >= n) - m = n - 1; - - assert(m > 0 && n > 1 && m < n); - - distances->m = m; - distances->n = n; - distances->distances = sr_malloc(sizeof(*distances->distances) * - (get_distance_position(distances, m - 1, n - 1) + 1)); - - return distances; -} - -struct sr_distances * -sr_distances_dup(struct sr_distances *distances) -{ - struct sr_distances *dup_distances; - - dup_distances = sr_distances_new(distances->m, distances->n); - memcpy(dup_distances->distances, distances->distances, - sizeof(*distances->distances) * - (get_distance_position(distances, distances->m - 1, distances->n - 1) + 1)); - - return dup_distances; -} - -void -sr_distances_free(struct sr_distances *distances) -{ - if (!distances) - return; - - free(distances->distances); - free(distances); -} - -float -sr_distances_get_distance(struct sr_distances *distances, int i, int j) -{ - if (i == j) - return 0.0; - - if (i > j) - { - int x; - x = j, j = i, i = x; - } - - return distances->distances[get_distance_position(distances, i, j)]; -} - -void -sr_distances_set_distance(struct sr_distances *distances, - int i, - int j, - float d) -{ - if (i == j) - return; - - if (i > j) - { - int x; - x = j, j = i, i = x; - } - - distances->distances[get_distance_position(distances, i, j)] = d; -} - -struct sr_distances * -sr_gdb_threads_compare(struct sr_gdb_thread **threads, - int m, - int n, - sr_dist_thread_type dist_func) -{ - struct sr_distances *distances; - struct sr_gdb_thread *thread1, *thread2; - int i, j, ok, all; - - distances = sr_distances_new(m, n); - - for (i = 0; i < m; i++) - { - for (j = i + 1; j < n; j++) - { - ok = all = 0; - sr_gdb_thread_quality_counts(threads[i], &ok, &all); - sr_gdb_thread_quality_counts(threads[j], &ok, &all); - - if (ok == all) - { - thread1 = threads[i]; - thread2 = threads[j]; - } - else - { - /* There are some unknown function names, try to pair them, but - * the threads need to be copied first. */ - thread1 = sr_gdb_thread_dup(threads[i], false); - thread2 = sr_gdb_thread_dup(threads[j], false); - sr_normalize_gdb_paired_unknown_function_names(thread1, thread2); - } - - distances->distances[get_distance_position(distances, i, j)] = dist_func(thread1, thread2); - - if (ok != all) - { - sr_gdb_thread_free(thread1); - sr_gdb_thread_free(thread2); - } - } - } - - return distances; -} diff --git a/python/py_metrics.c b/python/py_metrics.c index b733b3b..78403b2 100644 --- a/python/py_metrics.c +++ b/python/py_metrics.c @@ -1,7 +1,7 @@ #include "py_metrics.h" #include "py_gdb_thread.h" #include "strbuf.h" -#include "metrics.h" +#include "distance.h"
#define distances_doc "satyr.Distances - class representing distances between objects\n" \ "Usage:\n" \ @@ -103,7 +103,7 @@ sr_py_distances_new(PyTypeObject *object, PyObject *args, PyObject *kwds) if (PyArg_ParseTuple(args, "sO!i", &dist_name, &PyList_Type, &thread_list, &m)) { n = PyList_Size(thread_list); - struct sr_gdb_thread *threads[n]; + struct sr_thread *threads[n];
for (i = 0; i < n; i++) { @@ -119,7 +119,7 @@ sr_py_distances_new(PyTypeObject *object, PyObject *args, PyObject *kwds) { return NULL; } - threads[i] = to->thread; + threads[i] = (struct sr_thread*)to->thread; } if (m < 1 || n < 2) { @@ -127,19 +127,19 @@ sr_py_distances_new(PyTypeObject *object, PyObject *args, PyObject *kwds) return NULL; }
- sr_dist_thread_type dist_func; + enum sr_distance_type dist_type;
if (!strcmp(dist_name, "jaccard")) - dist_func = sr_gdb_thread_jaccard_distance; + dist_type = SR_DISTANCE_JACCARD; else if (!strcmp(dist_name, "levenshtein")) - dist_func = sr_gdb_thread_levenshtein_distance_f; + dist_type = SR_DISTANCE_LEVENSHTEIN; else { PyErr_SetString(PyExc_ValueError, "Unknown name of distance function"); return NULL; }
- o->distances = sr_gdb_threads_compare(threads, m, n, dist_func); + o->distances = sr_threads_compare(threads, m, n, dist_type); } else if (PyArg_ParseTuple(args, "ii", &m, &n)) { diff --git a/satyr.c b/satyr.c index 572ec3c..841ccdc 100644 --- a/satyr.c +++ b/satyr.c @@ -23,7 +23,6 @@ #include "utils.h" #include "location.h" #include "strbuf.h" -#include "metrics.h" #include "cluster.h" #include "normalize.h" #include "report.h" diff --git a/tests/cluster.at b/tests/cluster.at index ad0ddb7..ca5037a 100644 --- a/tests/cluster.at +++ b/tests/cluster.at @@ -2,7 +2,7 @@ AT_BANNER([Clustering])
AT_TESTFUN([sr_distances_cluster_objects], [ -#include "metrics.h" +#include "distance.h" #include "cluster.h" #include <assert.h> #include <stdio.h> @@ -71,7 +71,6 @@ main()
AT_TESTFUN([sr_dendrogram_cut], [ -#include "metrics.h" #include "cluster.h" #include <assert.h> #include <stdio.h> diff --git a/tests/metrics.at b/tests/metrics.at index 7f56fce..0d259aa 100644 --- a/tests/metrics.at +++ b/tests/metrics.at @@ -7,7 +7,6 @@ m4_define([UTILS], #include "utils.h" #include <stdlib.h> #include <assert.h> -#include "metrics.h" #include "normalize.h" #include "distance.h"
@@ -364,7 +363,7 @@ main() threads[[2]] = create_thread(3, "asd", "agd", "??"); threads[[3]] = create_thread(3, "dg", "??", "??");
- struct sr_distances *distances = sr_gdb_threads_compare(threads, 3, 4, sr_gdb_thread_jaccard_distance); + struct sr_distances *distances = sr_threads_compare(threads, 3, 4, SR_DISTANCE_JACCARD); assert(is_dist_equal(0.6, sr_distances_get_distance(distances, 0, 1))); assert(is_dist_equal(0.6, sr_distances_get_distance(distances, 0, 2))); assert(is_dist_equal(1.0, sr_distances_get_distance(distances, 0, 3))); diff --git a/tests/normalize.at b/tests/normalize.at index 4038ec8..d15a4fd 100644 --- a/tests/normalize.at +++ b/tests/normalize.at @@ -7,7 +7,6 @@ m4_define([UTILS], #include "gdb/thread.h" #include "gdb/frame.h" #include "utils.h" -#include "metrics.h" #include "normalize.h" #include <stdlib.h> #include <assert.h>
Pushed entire patch set. Thanks!
Note: I'd like to ask you to add some comments to sr_distances_* algorithms. I'm sure you understand the algorithms and the comments would save time for the next reader. For example get_distance_position() does some magic because the distance matrix is only a half of MxN matrix ...
On Fri, 2013-06-14 at 20:01 +0200, Martin Milata wrote:
This patchset adds two functions, sr_distance and sr_threads_compare, which allow you to compare two or multiple threads respectively. The threads can be of any type supported by satyr as long as all threads are of the same type.
The python bindings are not yet updated to accept any thread type -- I'd like to work on [0] first and then modify the python bindings in one go.
Please note that the patches depend on 'source-reorganization' branch sent earlier and won't apply without it. The code is also available at [1].
[0] https://github.com/abrt/satyr/issues/66 [1] https://github.com/abrt/satyr/commits/gh63-agnostic-distance
Martin Milata (6): Fix comment in thread.h Add sr_frame_cmp and sr_frame_cmp_distance Make thread distance type-agnostic distance: normalize levenshtein distance Port tests to type-agnostic distance functions Type-agnostic distance matrices
include/Makefile.am | 1 - include/distance.h | 121 ++++++++++---- include/frame.h | 14 ++ include/metrics.h | 219 -------------------------- include/thread.h | 7 +- lib/Makefile.am | 1 - lib/cluster.c | 2 +- lib/core_frame.c | 4 + lib/core_thread.c | 2 +- lib/distance.c | 406 ++++++++++++++++++++++------------------------- lib/gdb_frame.c | 8 + lib/gdb_thread.c | 2 +- lib/generic_frame.c | 18 +++ lib/generic_frame.h | 3 + lib/generic_thread.h | 4 +- lib/java_frame.c | 2 + lib/java_thread.c | 2 +- lib/koops_frame.c | 2 + lib/koops_stacktrace.c | 2 +- lib/metrics.c | 409 ------------------------------------------------ lib/python_frame.c | 2 + lib/python_stacktrace.c | 2 +- python/py_metrics.c | 14 +- satyr.c | 1 - tests/cluster.at | 3 +- tests/metrics.at | 54 +++---- tests/normalize.at | 1 - 27 files changed, 383 insertions(+), 923 deletions(-) delete mode 100644 include/metrics.h delete mode 100644 lib/metrics.c
crash-catcher@lists.fedorahosted.org