From 70407e861d8430dbe06cc52e6fe4ed5c9cd0872a Mon Sep 17 00:00:00 2001 From: Benjamin Poirier Date: Thu, 23 Jul 2009 17:59:24 -0400 Subject: [PATCH] Split the synchronization code into modules Separates synchronization code in processing, matching and analysis modules. There is also a "sync-chain" that coordinates module creation. Adds a "--sync-null" option, mainly for performance evaluation. Signed-off-by: Benjamin Poirier --- lttv/lttv/Makefile.am | 10 +- lttv/lttv/sync.c | 1986 ----------------- lttv/lttv/sync.h | 183 -- lttv/lttv/sync/data_structures_tcp.c | 385 ++++ lttv/lttv/sync/data_structures_tcp.h | 106 + lttv/lttv/sync/event_analysis.h | 42 + lttv/lttv/sync/event_analysis_linreg.c | 745 +++++++ lttv/lttv/sync/event_analysis_linreg.h | 52 + lttv/lttv/sync/event_matching.h | 42 + lttv/lttv/sync/event_matching_tcp.c | 501 +++++ lttv/lttv/sync/event_matching_tcp.h | 47 + lttv/lttv/sync/event_processing.h | 43 + lttv/lttv/sync/event_processing_lttv_common.c | 238 ++ lttv/lttv/sync/event_processing_lttv_common.h | 68 + lttv/lttv/sync/event_processing_lttv_null.c | 149 ++ lttv/lttv/sync/event_processing_lttv_null.h | 38 + .../sync/event_processing_lttv_standard.c | 582 +++++ .../sync/event_processing_lttv_standard.h | 55 + lttv/lttv/{ => sync}/lookup3.h | 0 lttv/lttv/sync/sync_chain.c | 329 +++ lttv/lttv/sync/sync_chain.h | 48 + .../gui/lttvwindow/lttvwindow/callbacks.c | 3 +- lttv/modules/text/batchAnalysis.c | 3 +- 23 files changed, 3482 insertions(+), 2173 deletions(-) delete mode 100644 lttv/lttv/sync.c delete mode 100644 lttv/lttv/sync.h create mode 100644 lttv/lttv/sync/data_structures_tcp.c create mode 100644 lttv/lttv/sync/data_structures_tcp.h create mode 100644 lttv/lttv/sync/event_analysis.h create mode 100644 lttv/lttv/sync/event_analysis_linreg.c create mode 100644 lttv/lttv/sync/event_analysis_linreg.h create mode 100644 lttv/lttv/sync/event_matching.h create mode 100644 lttv/lttv/sync/event_matching_tcp.c create mode 100644 lttv/lttv/sync/event_matching_tcp.h create mode 100644 lttv/lttv/sync/event_processing.h create mode 100644 lttv/lttv/sync/event_processing_lttv_common.c create mode 100644 lttv/lttv/sync/event_processing_lttv_common.h create mode 100644 lttv/lttv/sync/event_processing_lttv_null.c create mode 100644 lttv/lttv/sync/event_processing_lttv_null.h create mode 100644 lttv/lttv/sync/event_processing_lttv_standard.c create mode 100644 lttv/lttv/sync/event_processing_lttv_standard.h rename lttv/lttv/{ => sync}/lookup3.h (100%) create mode 100644 lttv/lttv/sync/sync_chain.c create mode 100644 lttv/lttv/sync/sync_chain.h diff --git a/lttv/lttv/Makefile.am b/lttv/lttv/Makefile.am index a522a33b..de0a170f 100644 --- a/lttv/lttv/Makefile.am +++ b/lttv/lttv/Makefile.am @@ -51,9 +51,15 @@ lttv_real_SOURCES = \ stats.c\ tracecontext.c\ traceset.c\ - sync.c\ filter.c\ - print.c + print.c\ + sync/sync_chain.c\ + sync/data_structures_tcp.c\ + sync/event_processing_lttv_common.c\ + sync/event_processing_lttv_standard.c\ + sync/event_processing_lttv_null.c\ + sync/event_matching_tcp.c\ + sync/event_analysis_linreg.c lttvinclude_HEADERS = \ attribute.h\ diff --git a/lttv/lttv/sync.c b/lttv/lttv/sync.c deleted file mode 100644 index 1379b412..00000000 --- a/lttv/lttv/sync.c +++ /dev/null @@ -1,1986 +0,0 @@ -/* This file is part of the Linux Trace Toolkit viewer - * Copyright (C) 2008 Benjamin Poirier - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License Version 2 as - * published by the Free Software Foundation; - * - * 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., 59 Temple Place - Suite 330, Boston, - * MA 02111-1307, USA. - */ - -// for INFINITY in math.h -#define _ISOC99_SOURCE - -#ifdef HAVE_CONFIG_H -#include -#endif - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include -#include - -#include "lookup3.h" - -#include "sync.h" - - -GQuark - LTT_CHANNEL_NET, - LTT_CHANNEL_NETIF_STATE; - -GQuark - LTT_EVENT_DEV_HARD_START_XMIT_TCP, - LTT_EVENT_DEV_RECEIVE, - LTT_EVENT_PKFREE_SKB, - LTT_EVENT_TCPV4_RCV, - LTT_EVENT_NETWORK_IPV4_INTERFACE; - -GQuark - LTT_FIELD_SKB, - LTT_FIELD_PROTOCOL, - LTT_FIELD_SADDR, - LTT_FIELD_DADDR, - LTT_FIELD_TOT_LEN, - LTT_FIELD_IHL, - LTT_FIELD_SOURCE, - LTT_FIELD_DEST, - LTT_FIELD_SEQ, - LTT_FIELD_ACK_SEQ, - LTT_FIELD_DOFF, - LTT_FIELD_ACK, - LTT_FIELD_RST, - LTT_FIELD_SYN, - LTT_FIELD_FIN, - LTT_FIELD_NAME, - LTT_FIELD_ADDRESS, - LTT_FIELD_UP; - -static gboolean optionSync; -static gboolean optionSyncStats; -static char* optionSyncData; - -/* - * Module init function - */ -static void init() -{ - g_debug("\t\t\tXXXX sync init\n"); - - LTT_CHANNEL_NET= g_quark_from_string("net"); - LTT_CHANNEL_NETIF_STATE= g_quark_from_string("netif_state"); - - LTT_EVENT_DEV_HARD_START_XMIT_TCP= - g_quark_from_string("dev_hard_start_xmit_tcp"); - LTT_EVENT_DEV_RECEIVE= g_quark_from_string("dev_receive"); - LTT_EVENT_PKFREE_SKB= g_quark_from_string("pkfree_skb"); - LTT_EVENT_TCPV4_RCV= g_quark_from_string("tcpv4_rcv"); - LTT_EVENT_NETWORK_IPV4_INTERFACE= - g_quark_from_string("network_ipv4_interface"); - - LTT_FIELD_SKB= g_quark_from_string("skb"); - LTT_FIELD_PROTOCOL= g_quark_from_string("protocol"); - LTT_FIELD_SADDR= g_quark_from_string("saddr"); - LTT_FIELD_DADDR= g_quark_from_string("daddr"); - LTT_FIELD_TOT_LEN= g_quark_from_string("tot_len"); - LTT_FIELD_IHL= g_quark_from_string("ihl"); - LTT_FIELD_SOURCE= g_quark_from_string("source"); - LTT_FIELD_DEST= g_quark_from_string("dest"); - LTT_FIELD_SEQ= g_quark_from_string("seq"); - LTT_FIELD_ACK_SEQ= g_quark_from_string("ack_seq"); - LTT_FIELD_DOFF= g_quark_from_string("doff"); - LTT_FIELD_ACK= g_quark_from_string("ack"); - LTT_FIELD_RST= g_quark_from_string("rst"); - LTT_FIELD_SYN= g_quark_from_string("syn"); - LTT_FIELD_FIN= g_quark_from_string("fin"); - LTT_FIELD_NAME= g_quark_from_string("name"); - LTT_FIELD_ADDRESS= g_quark_from_string("address"); - LTT_FIELD_UP= g_quark_from_string("up"); - - optionSync= FALSE; - lttv_option_add("sync", '\0', "synchronize the time between tracefiles " - "based on network communications", "none", LTTV_OPT_NONE, &optionSync, - NULL, NULL); - - optionSyncStats= FALSE; - lttv_option_add("sync-stats", '\0', "print statistics about the time " - "synchronization", "none", LTTV_OPT_NONE, &optionSyncStats, NULL, NULL); - - optionSyncData= NULL; - lttv_option_add("sync-data", '\0', "save information about every offset " - "identified", "pathname of the file where to save the offsets", - LTTV_OPT_STRING, &optionSyncData, NULL, NULL); -} - - -/* - * Module unload function - */ -static void destroy() -{ - g_debug("\t\t\tXXXX sync destroy\n"); - - lttv_option_remove("sync"); - lttv_option_remove("sync-stats"); - lttv_option_remove("sync-data"); -} - - -/* - * Calculate a traceset's drift and offset values based on network events - * - * Args: - * tsc: traceset - */ -void sync_traceset(LttvTracesetContext* const tsc) -{ - SyncState* syncState; - struct timeval startTime, endTime; - struct rusage startUsage, endUsage; - int retval; - - if (optionSync == FALSE) - { - g_debug("Not synchronizing traceset because option is disabled"); - return; - } - - if (optionSyncStats) - { - gettimeofday(&startTime, 0); - getrusage(RUSAGE_SELF, &startUsage); - } - - // Initialize data structures - syncState= malloc(sizeof(SyncState)); - syncState->tsc= tsc; - syncState->traceNb= lttv_traceset_number(tsc->ts); - - if (optionSyncStats) - { - syncState->stats= calloc(1, sizeof(Stats)); - } - - if (optionSyncData) - { - syncState->dataFd= fopen(optionSyncData, "w"); - if (syncState->dataFd == NULL) - { - perror(0); - goto out_free; - } - - fprintf(syncState->dataFd, "%10s %10s %21s %21s %21s\n", "ni", "nj", - "timoy", "dji", "eji"); - } - - // Process traceset - registerHooks(syncState); - - lttv_process_traceset_seek_time(tsc, ltt_time_zero); - lttv_process_traceset_middle(tsc, ltt_time_infinite, G_MAXULONG, NULL); - lttv_process_traceset_seek_time(tsc, ltt_time_zero); - - unregisterHooks(syncState); - - // Finalize the least-squares analysis - finalizeLSA(syncState); - - // Find a reference node and structure nodes in a graph - doGraphProcessing(syncState); - - // Calculate the resulting offset and drift between each trace and its - // reference and write those values to the LttTrace structures - calculateFactors(syncState); - - if (optionSyncData) - { - retval= fclose(syncState->dataFd); - if (retval != 0) - { - perror(0); - } - } - -out_free: - if (optionSyncStats) - { - printf("Stats:\n"); - // Received frames - printf("\ttotal received packets: %d\n", syncState->stats->totRecv); - // Received frames that are ip - printf("\ttotal received IP packets: %d\n", - syncState->stats->totRecvIp); - // Processed packets that are tcp - printf("\ttotal input events: %d\n", syncState->stats->totInE); - // Sent packets that are tcp - printf("\ttotal output events: %d\n", syncState->stats->totOutE); - // Input and output events were matched together - printf("\ttotal packets identified: %d\n", - syncState->stats->totPacket); - printf("\ttotal packets identified needing an acknowledge: %d\n", - syncState->stats->totPacketNeedAck); - // Four events are matched - printf("\ttotal packets fully acknowledged: %d\n", - syncState->stats->totExchangeEffective); - // Many packets were acknowledged at once - printf("\ttotal packets cummulatively acknowledged (excluding the " - "first in each series): %d\n", - syncState->stats->totPacketCummAcked); - // Offset calculations that could be done, some effective exchanges are - // not used when there is cummulative acknowledge - printf("\ttotal exchanges identified: %d\n", - syncState->stats->totExchangeReal); - - free(syncState->stats); - } - free(syncState); - - if (optionSyncStats) - { - gettimeofday(&endTime, 0); - retval= getrusage(RUSAGE_SELF, &endUsage); - - timeDiff(&endTime, &startTime); - timeDiff(&endUsage.ru_utime, &startUsage.ru_utime); - timeDiff(&endUsage.ru_stime, &startUsage.ru_stime); - - printf("Synchronization time:\n"); - printf("\treal time: %ld.%06ld\n", endTime.tv_sec, endTime.tv_usec); - printf("\tuser time: %ld.%06ld\n", endUsage.ru_utime.tv_sec, endUsage.ru_utime.tv_usec); - printf("\tsystem time: %ld.%06ld\n", endUsage.ru_stime.tv_sec, endUsage.ru_stime.tv_usec); - } -} - - -/* - * Allocate and initialize data structures for synchronizing a traceset. - * Register event hooks. - * - * Args: - * syncState: container for synchronization data. - * This function allocates theses members: - * traceNumTable - * hookListList - * pendingRecv - * unMatchedInE - * unMatchedOutE - * unAcked - * fitArray - */ -void registerHooks(SyncState* const syncState) -{ - unsigned int i, j, k; - - // Allocate lists - syncState->pendingRecv= g_hash_table_new_full(NULL, NULL, NULL, - &netEventListDestroy); - syncState->unMatchedInE= g_hash_table_new_full(&netEventPacketHash, - &netEventPacketEqual, NULL, &ghtDestroyNetEvent); - syncState->unMatchedOutE= g_hash_table_new_full(&netEventPacketHash, - &netEventPacketEqual, NULL, &ghtDestroyNetEvent); - syncState->unAcked= g_hash_table_new_full(&connectionHash, - &connectionEqual, &connectionDestroy, &packetListDestroy); - - syncState->fitArray= malloc(syncState->traceNb * sizeof(Fit*)); - for (i= 0; i < syncState->traceNb; i++) - { - syncState->fitArray[i]= calloc(syncState->traceNb, sizeof(Fit)); - } - - syncState->traceNumTable= g_hash_table_new(&g_direct_hash, - &g_direct_equal); - - syncState->hookListList= g_array_sized_new(FALSE, FALSE, sizeof(GArray*), - syncState->traceNb); - - // Add event hooks and initialize traceNumTable - // note: possibilité de remettre le code avec lttv_trace_find_marker_ids (voir r328) - for(i= 0; i < syncState->traceNb; i++) - { - guint old_len; - LttvTraceContext* tc; - GArray* hookList; - const int hookNb= 5; - int retval; - - hookList= g_array_sized_new(FALSE, FALSE, sizeof(LttvTraceHook), hookNb); - g_array_append_val(syncState->hookListList, hookList); - - tc= syncState->tsc->traces[i]; - - g_hash_table_insert(syncState->traceNumTable, tc->t, (gpointer) i); - - // Find the hooks - old_len= hookList->len; - retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NET, - LTT_EVENT_DEV_HARD_START_XMIT_TCP, - FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_SADDR, - LTT_FIELD_DADDR, LTT_FIELD_TOT_LEN, - LTT_FIELD_IHL, LTT_FIELD_SOURCE, - LTT_FIELD_DEST, LTT_FIELD_SEQ, - LTT_FIELD_ACK_SEQ, LTT_FIELD_DOFF, - LTT_FIELD_ACK, LTT_FIELD_RST, LTT_FIELD_SYN, - LTT_FIELD_FIN), process_event_by_id, - syncState, &hookList); - if (retval != 0) - { - g_warning("Trace %d contains no %s.%s marker\n", i, - g_quark_to_string(LTT_CHANNEL_NET), - g_quark_to_string(LTT_EVENT_DEV_HARD_START_XMIT_TCP)); - } - else - { - g_assert(hookList->len - old_len == 1); - } - - old_len= hookList->len; - retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NET, - LTT_EVENT_DEV_RECEIVE, FIELD_ARRAY(LTT_FIELD_SKB, - LTT_FIELD_PROTOCOL), process_event_by_id, syncState, &hookList); - if (retval != 0) - { - g_warning("Trace %d contains no %s.%s marker\n", i, - g_quark_to_string(LTT_CHANNEL_NET), - g_quark_to_string(LTT_EVENT_DEV_RECEIVE)); - } - else - { - g_assert(hookList->len - old_len == 1); - } - - old_len= hookList->len; - retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NET, - LTT_EVENT_PKFREE_SKB, FIELD_ARRAY(LTT_FIELD_SKB), - process_event_by_id, syncState, &hookList); - if (retval != 0) - { - g_warning("Trace %d contains no %s.%s marker\n", i, - g_quark_to_string(LTT_CHANNEL_NET), - g_quark_to_string(LTT_EVENT_PKFREE_SKB)); - } - else - { - g_assert(hookList->len - old_len == 1); - } - - old_len= hookList->len; - retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NET, LTT_EVENT_TCPV4_RCV, - FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_SADDR, LTT_FIELD_DADDR, - LTT_FIELD_TOT_LEN, LTT_FIELD_IHL, LTT_FIELD_SOURCE, - LTT_FIELD_DEST, LTT_FIELD_SEQ, LTT_FIELD_ACK_SEQ, - LTT_FIELD_DOFF, LTT_FIELD_ACK, LTT_FIELD_RST, LTT_FIELD_SYN, - LTT_FIELD_FIN), process_event_by_id, syncState, &hookList); - if (retval != 0) - { - g_warning("Trace %d contains no %s.%s marker\n", i, - g_quark_to_string(LTT_CHANNEL_NET), - g_quark_to_string(LTT_EVENT_TCPV4_RCV)); - } - else - { - g_assert(hookList->len - old_len == 1); - } - - old_len= hookList->len; - retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NETIF_STATE, - LTT_EVENT_NETWORK_IPV4_INTERFACE, FIELD_ARRAY(LTT_FIELD_NAME, - LTT_FIELD_ADDRESS, LTT_FIELD_UP), process_event_by_id, syncState, - &hookList); - if (retval != 0) - { - g_warning("Trace %d contains no %s.%s marker\n", i, - g_quark_to_string(LTT_CHANNEL_NETIF_STATE), - g_quark_to_string(LTT_EVENT_NETWORK_IPV4_INTERFACE)); - } - else - { - g_assert(hookList->len - old_len == 1); - } - - // Add the hooks to each tracefile's event_by_id hook list - for(j= 0; j < tc->tracefiles->len; j++) - { - LttvTracefileContext* tfc; - - tfc= g_array_index(tc->tracefiles, LttvTracefileContext*, j); - - for(k= 0; k < hookList->len; k++) - { - LttvTraceHook* trace_hook; - - trace_hook= &g_array_index(hookList, LttvTraceHook, k); - if (trace_hook->hook_data != syncState) - { - g_assert_not_reached(); - } - if (trace_hook->mdata == tfc->tf->mdata) - { - lttv_hooks_add(lttv_hooks_by_id_find(tfc->event_by_id, - trace_hook->id), - trace_hook->h, trace_hook, - LTTV_PRIO_DEFAULT); - } - } - } - } -} - - -/* - * Unregister event hooks. Deallocate some data structures that are not needed - * anymore after running the hooks. - * Args: - * syncState: container for synchronization data. - * This function deallocates theses members: - * hookListList - * pendingRecv - * unMatchedInE - * unMatchedOutE - * unAcked - */ -void unregisterHooks(SyncState* const syncState) -{ - unsigned int i, j, k; - - // Remove event hooks - for(i= 0; i < syncState->traceNb; i++) - { - LttvTraceContext* tc; - GArray* hookList; - - tc= syncState->tsc->traces[i]; - hookList= g_array_index(syncState->hookListList, GArray*, i); - - // Remove the hooks from each tracefile's event_by_id hook list - for(j= 0; j < tc->tracefiles->len; j++) - { - LttvTracefileContext* tfc; - - tfc= g_array_index(tc->tracefiles, LttvTracefileContext*, j); - - for(k= 0; k < hookList->len; k++) - { - LttvTraceHook* trace_hook; - - trace_hook= &g_array_index(hookList, LttvTraceHook, k); - if (trace_hook->mdata == tfc->tf->mdata) - { - lttv_hooks_remove_data(lttv_hooks_by_id_find(tfc->event_by_id, - trace_hook->id), trace_hook->h, trace_hook); - } - } - } - - g_array_free(hookList, TRUE); - } - - g_array_free(syncState->hookListList, TRUE); - - // Free lists - g_debug("Cleaning up pendingRecv list\n"); - g_hash_table_destroy(syncState->pendingRecv); - g_debug("Cleaning up unMatchedInE list\n"); - g_hash_table_destroy(syncState->unMatchedInE); - g_debug("Cleaning up unMatchedOutE list\n"); - g_hash_table_destroy(syncState->unMatchedOutE); - g_debug("Cleaning up unAcked list\n"); - g_hash_table_destroy(syncState->unAcked); -} - - -/* - * Finalize the least-squares analysis. The intermediate values in the fit - * array are used to calculate the drift and the offset between each pair of - * nodes based on their exchanges. - * - * Args: - * syncState: container for synchronization data. - */ -void finalizeLSA(SyncState* const syncState) -{ - unsigned int i, j; - - if (optionSyncStats) - { - printf("Individual synchronization factors:\n"); - } - - for (i= 0; i < syncState->traceNb; i++) - { - for (j= 0; j < syncState->traceNb; j++) - { - if (i != j) - { - Fit* fit; - double delta; - - fit= &syncState->fitArray[i][j]; - - delta= fit->n * fit->st2 - pow(fit->st, 2); - fit->x= (fit->n * fit->std - fit->st * fit->sd) / delta; - fit->d0= (fit->st2 * fit->sd - fit->st * fit->std) / delta; - fit->e= sqrt((fit->sd2 - (fit->n * pow(fit->std, 2) + - pow(fit->sd, 2) * fit->st2 - 2 * fit->st * fit->sd - * fit->std) / delta) / (fit->n - 2)); - - g_debug("[i= %u j= %u]\n", i, j); - g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g\n", - fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std); - g_debug("xij= %g d0ij= %g e= %g\n", fit->x, fit->d0, fit->e); - g_debug("(xji= %g d0ji= %g)\n", -fit->x / (1 + fit->x), - -fit->d0 / (1 + fit->x)); - } - } - } - - if (optionSyncStats) - { - for (i= 0; i < syncState->traceNb; i++) - { - for (j= 0; j < syncState->traceNb; j++) - { - if (i < j) - { - Fit* fit; - - fit= &syncState->fitArray[i][j]; - printf("\tbetween trace i= %u and j= %u, xij= %g d0ij= %g " - "e= %g\n", i, j, fit->x, fit->d0, fit->e); - - fit= &syncState->fitArray[j][i]; - printf("\tbetween trace i= %u and j= %u, xij= %g d0ij= %g " - "e= %g\n", j, i, fit->x, fit->d0, fit->e); - } - } - } - } -} - - -/* - * Structure nodes in graphs of nodes that had exchanges. Each graph has a - * reference node, the one that can reach the others with the smallest - * cummulative error. - * - * Args: - * syncState: container for synchronization data. - * This function allocates these members: - * graphList - */ -void doGraphProcessing(SyncState* const syncState) -{ - unsigned int i, j; - double* distances; - unsigned int* previousVertex; - - distances= malloc(syncState->traceNb * sizeof(double)); - previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); - syncState->graphList= g_queue_new(); - - for (i= 0; i < syncState->traceNb; i++) - { - double errorSum; - GList* result; - - // Perform shortest path search - g_debug("shortest path trace %d\ndistances: ", i); - shortestPath(syncState->fitArray, i, syncState->traceNb, distances, - previousVertex); - - for (j= 0; j < syncState->traceNb; j++) - { - g_debug("%g, ", distances[j]); - } - g_debug("\npreviousVertex: "); - for (j= 0; j < syncState->traceNb; j++) - { - g_debug("%u, ", previousVertex[j]); - } - g_debug("\n"); - - // Group in graphs nodes that have exchanges - errorSum= sumDistances(distances, syncState->traceNb); - result= g_queue_find_custom(syncState->graphList, &i, - &graphTraceCompare); - if (result != NULL) - { - Graph* graph; - - g_debug("found graph\n"); - graph= (Graph*) result->data; - if (errorSum < graph->errorSum) - { - g_debug("adding to graph\n"); - graph->errorSum= errorSum; - free(graph->previousVertex); - graph->previousVertex= previousVertex; - graph->reference= i; - previousVertex= malloc(syncState->traceNb * sizeof(unsigned - int)); - } - } - else - { - Graph* newGraph; - - g_debug("creating new graph\n"); - newGraph= malloc(sizeof(Graph)); - newGraph->errorSum= errorSum; - newGraph->previousVertex= previousVertex; - newGraph->reference= i; - previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); - - g_queue_push_tail(syncState->graphList, newGraph); - } - } - - free(previousVertex); - free(distances); -} - - -/* - * Calculate the resulting offset and drift between each trace and its - * reference and write those values to the LttTrace structures. Also free - * structures that are not needed anymore. - * - * Args: - * syncState: container for synchronization data. - * This function deallocates: - * traceNumTable - * fitArray - * graphList - */ -void calculateFactors(SyncState* const syncState) -{ - unsigned int i, j; - double minOffset; - - // Calculate the resulting offset and drift between each trace and its - // reference - g_info("Factors:\n"); - if (optionSyncStats) - { - printf("Resulting synchronization factors:\n"); - } - - minOffset= 0; - for (i= 0; i < syncState->traceNb; i++) - { - GList* result; - - result= g_queue_find_custom(syncState->graphList, &i, - &graphTraceCompare); - if (result != NULL) - { - Graph* graph; - double drift, offset, stDev; - LttTrace* t; - - t= syncState->tsc->traces[i]->t; - graph= (Graph*) result->data; - - g_info("trace %u (%p) graph: reference %u\n", i, t, graph->reference); - - for (j= 0; j < syncState->traceNb; j++) - { - g_info("%u, ", graph->previousVertex[j]); - } - g_info("\n"); - - factors(syncState->fitArray, graph->previousVertex, i, &drift, - &offset, &stDev); - t->drift= drift; - t->offset= offset; - t->start_time_from_tsc = - ltt_time_from_uint64(tsc_to_uint64(t->freq_scale, - t->start_freq, drift * t->start_tsc + offset)); - - if (optionSyncStats) - { - if (i == graph->reference) - { - printf("\ttrace %u reference %u previous vertex - " - "stdev= %g\n", i, - graph->reference, stDev); - } - else - { - printf("\ttrace %u reference %u previous vertex %u " - "stdev= %g\n", i, - graph->reference, - graph->previousVertex[i], - stDev); - } - } - - if (offset < minOffset) - { - minOffset= offset; - } - } - else - { - fprintf(stderr, "trace: %d\n", i); - g_assert_not_reached(); - } - } - - // Adjust all offsets so the lowest one is 0 (no negative offsets) - for (i= 0; i < syncState->traceNb; i++) - { - LttTrace* t; - - t= syncState->tsc->traces[i]->t; - t->offset-= minOffset; - t->start_time_from_tsc = - ltt_time_from_uint64(tsc_to_uint64(t->freq_scale, - t->start_freq, t->drift * t->start_tsc - + t->offset)); - - g_info("trace %u drift: %f offset: %g start_time: %ld.%09ld\n", - i, t->drift, t->offset, t->start_time_from_tsc.tv_sec, - t->start_time_from_tsc.tv_nsec); - - if (optionSyncStats) - { - printf("\ttrace %u drift= %g offset= %g (%f)\n", i, - t->drift, t->offset, - tsc_to_uint64(t->freq_scale, t->start_freq, - t->offset) / 1e9); - } - } - - lttv_traceset_context_compute_time_span(syncState->tsc, - &syncState->tsc->time_span); - - g_debug("traceset start %ld.%09ld end %ld.%09ld\n", - syncState->tsc->time_span.start_time.tv_sec, - syncState->tsc->time_span.start_time.tv_nsec, - syncState->tsc->time_span.end_time.tv_sec, - syncState->tsc->time_span.end_time.tv_nsec); - - g_queue_foreach(syncState->graphList, &graphRemove, NULL); - g_queue_free(syncState->graphList); - - for (i= 0; i < syncState->traceNb; i++) - { - free(syncState->fitArray[i]); - } - free(syncState->fitArray); - - g_hash_table_destroy(syncState->traceNumTable); -} - - -/* - * Lttv hook function that will be called for network events - * - * Args: - * hook_data: LttvTraceHook* for the type of event that generated the call - * call_data: LttvTracefileContext* at the moment of the event - * - * Returns: - * FALSE Always returns FALSE, meaning to keep processing hooks for - * this event - */ -static gboolean process_event_by_id(void* hook_data, void* call_data) -{ - LttvTraceHook* trace_hook; - LttvTracefileContext* tfc; - LttEvent* event; - LttTime time; - LttCycleCount tsc; - LttTrace* trace; - struct marker_info* info; - SyncState* syncState; - - trace_hook= (LttvTraceHook*) hook_data; - tfc= (LttvTracefileContext*) call_data; - syncState= (SyncState*) trace_hook->hook_data; - event= ltt_tracefile_get_event(tfc->tf); - time= ltt_event_time(event); - tsc= ltt_event_cycle_count(event); - trace= tfc->t_context->t; - info= marker_get_info_from_id(tfc->tf->mdata, event->event_id); - - g_debug("XXXX process event: time: %ld.%09ld trace: %p name: %s ", - (long) time.tv_sec, time.tv_nsec, trace, - g_quark_to_string(info->name)); - - if (info->name == LTT_EVENT_DEV_HARD_START_XMIT_TCP) - { - NetEvent* outE; - - if (optionSyncStats) - { - syncState->stats->totOutE++; - } - - outE= malloc(sizeof(NetEvent)); - - outE->packet= NULL; - outE->trace= trace; - outE->tsc= tsc; - - matchEvents(outE, syncState->unMatchedOutE, syncState->unMatchedInE, - event, trace_hook, offsetof(Packet, outE)); - - g_debug("Output event done\n"); - } - else if (info->name == LTT_EVENT_DEV_RECEIVE) - { - NetEvent* inE; - guint64 protocol; - - if (optionSyncStats) - { - syncState->stats->totRecv++; - } - - protocol= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 1)); - - if (protocol == ETH_P_IP) - { - GQueue* list; - - if (optionSyncStats) - { - syncState->stats->totRecvIp++; - } - - inE= malloc(sizeof(NetEvent)); - - inE->packet= NULL; - inE->trace= trace; - inE->tsc= tsc; - inE->skb= (void*) (unsigned long) - ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 0)); - - list= g_hash_table_lookup(syncState->pendingRecv, trace); - if (unlikely(list == NULL)) - { - g_hash_table_insert(syncState->pendingRecv, trace, list= - g_queue_new()); - } - g_queue_push_head(list, inE); - - g_debug("Adding inE to pendingRecv\n"); - } - else - { - g_debug("\n"); - } - } - else if (info->name == LTT_EVENT_TCPV4_RCV) - { - GQueue* prList; - - // Search pendingRecv for an event with the same skb - prList= g_hash_table_lookup(syncState->pendingRecv, trace); - if (unlikely(prList == NULL)) - { - g_debug("No pending receive event list for this trace\n"); - } - else - { - NetEvent tempInE; - GList* result; - - tempInE.skb= (void*) (unsigned long) - ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 0)); - result= g_queue_find_custom(prList, &tempInE, &netEventSkbCompare); - - if (result == NULL) - { - g_debug("No matching pending receive event found\n"); - } - else - { - NetEvent* inE; - - if (optionSyncStats) - { - syncState->stats->totInE++; - } - - // If it's there, remove it and proceed with a receive event - inE= (NetEvent*) result->data; - g_queue_delete_link(prList, result); - - matchEvents(inE, syncState->unMatchedInE, - syncState->unMatchedOutE, event, trace_hook, - offsetof(Packet, inE)); - - g_debug("Input event done\n"); - } - } - } - else if (info->name == LTT_EVENT_PKFREE_SKB) - { - GQueue* list; - - list= g_hash_table_lookup(syncState->pendingRecv, trace); - if (unlikely(list == NULL)) - { - g_debug("No pending receive event list for this trace\n"); - } - else - { - NetEvent tempInE; - GList* result; - - tempInE.skb= (void*) (unsigned long) - ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 0)); - result= g_queue_find_custom(list, &tempInE, &netEventSkbCompare); - - if (result == NULL) - { - g_debug("No matching pending receive event found, \"shaddow" - "skb\"\n"); - } - else - { - NetEvent* inE; - - inE= (NetEvent*) result->data; - g_queue_delete_link(list, result); - destroyNetEvent(inE); - - g_debug("Non-TCP skb\n"); - } - } - } - else if (info->name == LTT_EVENT_NETWORK_IPV4_INTERFACE) - { - char* name; - guint64 address; - gint64 up; - char addressString[17]; - - name= ltt_event_get_string(event, lttv_trace_get_hook_field(trace_hook, - 0)); - address= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 1)); - up= ltt_event_get_long_int(event, lttv_trace_get_hook_field(trace_hook, - 2)); - - convertIP(addressString, address); - - g_debug("name \"%s\" address %s up %lld\n", name, addressString, up); - } - else - { - g_debug("\n"); - } - - return FALSE; -} - - -/* - * Implementation of a packet matching algorithm for TCP - * - * Args: - * netEvent new event to match - * unMatchedList list of unmatched events of the same type (send or receive) - * as netEvent - * unMatchedOppositeList list of unmatched events of the opposite type of - * netEvent - * event event corresponding to netEvent - * trace_hook trace_hook corresponding to netEvent - * fieldOffset offset of the NetEvent field in the Packet struct for the - * field of the type of netEvent - */ -static void matchEvents(NetEvent* const netEvent, GHashTable* const - unMatchedList, GHashTable* const unMatchedOppositeList, LttEvent* const - event, LttvTraceHook* const trace_hook, const size_t fieldOffset) -{ - Packet* packet; - GQueue* uaList; - GList* result; - SyncState* syncState; - NetEvent* companionEvent; - - syncState= (SyncState*) trace_hook->hook_data; - - // Search unmatched list of opposite type for a matching event - packet= malloc(sizeof(Packet)); - packet->connKey.saddr= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 1)); - packet->connKey.daddr= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 2)); - packet->tot_len= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 3)); - packet->ihl= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 4)); - packet->connKey.source= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 5)); - packet->connKey.dest= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 6)); - packet->seq= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 7)); - packet->ack_seq= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 8)); - packet->doff= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 9)); - packet->ack= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 10)); - packet->rst= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 11)); - packet->syn= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 12)); - packet->fin= ltt_event_get_long_unsigned(event, - lttv_trace_get_hook_field(trace_hook, 13)); - packet->inE= packet->outE= NULL; - packet->acks= NULL; - - companionEvent= g_hash_table_lookup(unMatchedOppositeList, packet); - if (companionEvent != NULL) - { - if (optionSyncStats) - { - syncState->stats->totPacket++; - } - - g_debug("Found matching companion event, "); - // If it's there, remove it and update the structures - g_hash_table_steal(unMatchedOppositeList, packet); - free(packet); - packet= companionEvent->packet; - *((NetEvent**) ((void*) packet + fieldOffset))= netEvent; - - // If this packet acknowleges some data ... - if (isAck(packet)) - { - uaList= g_hash_table_lookup(syncState->unAcked, &packet->connKey); - if (uaList != NULL) - { - Packet* ackedPacket; - - result= g_queue_find_custom(uaList, packet, &packetAckCompare); - - while (result != NULL) - { - // Remove the acknowledged packet from the unAcked list - // and keep this packet for later offset calculations - g_debug("Found matching unAcked packet, "); - - ackedPacket= (Packet*) result->data; - g_queue_delete_link(uaList, result); - - // If the acked packet doesn't have both of its events, - // remove the orphaned event from the corresponding - // unmatched list and destroy the acked packet (an event - // was not in the trace) - if (ackedPacket->inE == NULL) - { - g_hash_table_steal(syncState->unMatchedOutE, packet); - destroyPacket(ackedPacket); - } - else if (ackedPacket->outE == NULL) - { - g_hash_table_steal(syncState->unMatchedInE, packet); - destroyPacket(ackedPacket); - } - else - { - if (optionSyncStats) - { - syncState->stats->totExchangeEffective++; - } - - if (packet->acks == NULL) - { - packet->acks= g_queue_new(); - } - else if (optionSyncStats) - { - syncState->stats->totPacketCummAcked++; - } - - g_queue_push_tail(packet->acks, ackedPacket); - } - - result= g_queue_find_custom(uaList, packet, - &packetAckCompare); - } - - // It might be possible to do an offset calculation - if (packet->acks != NULL) - { - if (optionSyncStats) - { - syncState->stats->totExchangeReal++; - } - - g_debug("Synchronization calculation, "); - g_debug("%d acked packets - using last one, ", - g_queue_get_length(packet->acks)); - - ackedPacket= g_queue_peek_tail(packet->acks); - if (ackedPacket->outE->trace != packet->inE->trace || - ackedPacket->inE->trace != packet->outE->trace) - { - g_debug("disorganized exchange - discarding, "); - } - else if (ackedPacket->outE->trace == - ackedPacket->inE->trace) - { - g_debug("packets from the same trace - discarding, "); - } - else - { - double dji, eji; - double timoy; - unsigned int ni, nj; - LttTrace* orig_key; - Fit* fit; - - // Calculate the intermediate values for the - // least-squares analysis - dji= ((double) ackedPacket->inE->tsc - (double) - ackedPacket->outE->tsc + (double) packet->outE->tsc - - (double) packet->inE->tsc) / 2; - eji= fabs((double) ackedPacket->inE->tsc - (double) - ackedPacket->outE->tsc - (double) packet->outE->tsc - + (double) packet->inE->tsc) / 2; - timoy= ((double) ackedPacket->outE->tsc + (double) - packet->inE->tsc) / 2; - g_assert(g_hash_table_lookup_extended(syncState->traceNumTable, - ackedPacket->outE->trace, (gpointer*) - &orig_key, (gpointer*) &ni)); - g_assert(g_hash_table_lookup_extended(syncState->traceNumTable, - ackedPacket->inE->trace, (gpointer*) - &orig_key, (gpointer*) &nj)); - fit= &syncState->fitArray[nj][ni]; - - fit->n++; - fit->st+= timoy; - fit->st2+= pow(timoy, 2); - fit->sd+= dji; - fit->sd2+= pow(dji, 2); - fit->std+= timoy * dji; - - g_debug("intermediate values: dji= %f ti moy= %f " - "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f " - "sd2= %f std= %f, ", dji, timoy, ni, nj, fit->n, - fit->st, fit->st2, fit->sd, fit->sd2, fit->std); - - if (optionSyncData) - { - double freq; - - freq= syncState->tsc->traces[ni]->t->start_freq * - syncState->tsc->traces[ni]->t->freq_scale; - - fprintf(syncState->dataFd, "%10u %10u %21.10f %21.10f %21.10f\n", ni, - nj, timoy / freq, dji / freq, eji / freq); - } - } - } - } - } - - if (needsAck(packet)) - { - if (optionSyncStats) - { - syncState->stats->totPacketNeedAck++; - } - - // If this packet will generate an ack, add it to the unAcked list - g_debug("Adding to unAcked, "); - uaList= g_hash_table_lookup(syncState->unAcked, &packet->connKey); - if (uaList == NULL) - { - ConnectionKey* connKey; - - connKey= malloc(sizeof(ConnectionKey)); - memcpy(connKey, &packet->connKey, sizeof(ConnectionKey)); - g_hash_table_insert(syncState->unAcked, connKey, uaList= g_queue_new()); - } - g_queue_push_tail(uaList, packet); - } - else - { - destroyPacket(packet); - } - } - else - { - // If there's no corresponding event, finish creating the data - // structures and add an event to the unmatched list for this type of - // event - netEvent->packet= packet; - *((NetEvent**) ((void*) packet + fieldOffset))= netEvent; - - g_debug("Adding to unmatched event list, "); - g_hash_table_insert(unMatchedList, packet, netEvent); - } -} - - -/* - * Check if a packet is an acknowledge - * - * Returns: - * true if it is, - * false otherwise - */ -static bool isAck(const Packet* const packet) -{ - if (packet->ack == 1) - { - return true; - } - else - { - return false; - } -} - - -/* - * Check if a packet is an acknowledge of another packet. - * - * Args: - * ackPacket packet that is the confirmation - * ackedPacket packet that contains the original data, both packets have to - * come from the same connection - */ -static bool isAcking(const Packet* const ackPacket, const Packet* const ackedPacket) -{ - if (ackedPacket->connKey.saddr == ackPacket->connKey.daddr && - ackedPacket->connKey.daddr == ackPacket->connKey.saddr && - ackedPacket->connKey.source == ackPacket->connKey.dest && - ackedPacket->connKey.dest == ackPacket->connKey.source && - ackPacket->ack_seq > ackedPacket->seq) - { - return true; - } - else - { - return false; - } -} - - -/* - * Check if a packet will increment the sequence number, thus needing an - * acknowledge - * - * Returns: - * true if the packet will need an acknowledge - * false otherwise - */ -static bool needsAck(const Packet* const packet) -{ - if (packet->syn || packet->fin || packet->tot_len - packet->ihl * 4 - - packet->doff * 4 > 0) - { - return true; - } - else - { - return false; - } -} - - -/* - * Compare two ConnectionKey structures - * - * Returns: - * true if each field of the structure is equal - * false otherwise - */ -static bool connectionKeyEqual(const ConnectionKey* const a, const ConnectionKey* const b) -{ - if (a->saddr == b->saddr && a->daddr == b->daddr && a->source == - b->source && a->dest == b->dest) - { - return true; - } - else - { - return false; - } -} - - -/* - * A GDestroyNotify function for g_hash_table_new_full() - * - * Args: - * data: GQueue* list[NetEvent] - */ -static void netEventListDestroy(gpointer data) -{ - GQueue* list; - - list= (GQueue*) data; - - g_debug("XXXX netEventListDestroy\n"); - g_queue_foreach(list, &netEventRemove, NULL); - g_queue_free(list); -} - - -/* - * A GFunc for g_queue_foreach() - * - * Args: - * data: NetEvent* event - * user_data: NULL - */ -static void netEventRemove(gpointer data, gpointer user_data) -{ - destroyNetEvent((NetEvent*) data); -} - - -/* - * A GHashFunc for g_hash_table_new() - * - * This function is for indexing netEvents in unMatched lists. All fields of - * the corresponding packet must match for two keys to be equal. - * - * Args: - * key Packet* - */ -static guint netEventPacketHash(gconstpointer key) -{ - const Packet* p; - uint32_t a, b, c; - - p= key; - - a= p->connKey.source + (p->connKey.dest << 16); - b= p->connKey.saddr; - c= p->connKey.daddr; - mix(a, b, c); - - a+= p->tot_len; - b+= p->ihl; - c+= p->seq; - mix(a, b, c); - - a+= p->ack_seq; - b+= p->doff; - c+= p->ack; - mix(a, b, c); - - a+= p->rst; - b+= p->syn; - c+= p->fin; - final(a, b, c); - - return c; -} - - -/* - * A GEqualFunc for g_hash_table_new() - * - * This function is for indexing netEvents in unMatched lists. All fields of - * the corresponding packet must match for two keys to be equal. - * - * Args: - * a, b Packet* - * - * Returns: - * TRUE if both values are equal - */ -static gboolean netEventPacketEqual(gconstpointer a, gconstpointer b) -{ - const Packet* pA, * pB; - - pA= a; - pB= b; - - if (connectionKeyEqual(&pA->connKey, &pB->connKey) && - pA->tot_len == pB->tot_len && - pA->ihl == pB->ihl && - pA->seq == pB->seq && - pA->ack_seq == pB->ack_seq && - pA->doff == pB->doff && - pA->ack == pB->ack && - pA->rst == pB->rst && - pA->syn == pB->syn && - pA->fin == pB->fin) - { - return TRUE; - } - else - { - return FALSE; - } -} - - -/* - * A GDestroyNotify function for g_hash_table_new_full() - * - * Args: - * data: NetEvent* - */ -static void ghtDestroyNetEvent(gpointer data) -{ - destroyNetEvent((NetEvent*) data); -} - - -/* - * A GDestroyNotify function for g_hash_table_new_full() - * - * Args: - * data: GQueue* list[Packet] - */ -static void packetListDestroy(gpointer data) -{ - GQueue* list; - - list= (GQueue*) data; - - g_debug("XXXX packetListDestroy\n"); - - g_queue_foreach(list, &packetRemove, NULL); - g_queue_free(list); -} - - -/* - * A GFunc for g_queue_foreach() - * - * Args: - * data Packet*, packet to destroy - * user_data NULL - */ -static void packetRemove(gpointer data, gpointer user_data) -{ - Packet* packet; - - packet= (Packet*) data; - - g_debug("XXXX packetRemove\n"); - destroyPacket(packet); -} - - -/* - * Free the memory used by a Packet and the memory of all its associated - * resources - */ -static void destroyPacket(Packet* const packet) -{ - g_debug("XXXX destroyPacket "); - printPacket(packet); - g_debug("\n"); - - if (packet->inE) - { - free(packet->inE); - } - - if (packet->outE) - { - free(packet->outE); - } - - if (packet->acks) - { - g_queue_foreach(packet->acks, &packetRemove, NULL); - g_queue_free(packet->acks); - } - - free(packet); -} - - -/* - * Free the memory used by a NetEvent and the memory of all its associated - * resources. If the netEvent is part of a packet that also contains the other - * netEvent, that one will be freed also. Beware not to keep references to that - * other one. - */ -static void destroyNetEvent(NetEvent* const event) -{ - g_debug("XXXX destroyNetEvent\n"); - if (event->packet) - { - destroyPacket(event->packet); - } - else - { - free(event); - } -} - - -/* - * A GFunc for g_queue_foreach() - * - * Args: - * data Graph*, graph to destroy - * user_data NULL - */ -static void graphRemove(gpointer data, gpointer user_data) -{ - Graph* graph; - - graph= (Graph*) data; - - free(graph->previousVertex); - free(graph); -} - - -/* - * A GCompareFunc for g_queue_find_custom() - * - * Args: - * a: NetEvent* - * b: NetEvent* - * - * Returns - * 0 if the two events have the same skb - */ -static gint netEventSkbCompare(gconstpointer a, gconstpointer b) -{ - if (((NetEvent*) a)->skb == ((NetEvent*) b)->skb) - { - return 0; - } - else - { - return 1; - } -} - - -/* - * A GCompareFunc to be used with g_queue_find_custom() - * - * Args: - * a NetEvent* - * b NetEvent* - * - * Returns: - * 0 if the two net events correspond to the send and receive events of the - * same packet - */ -static gint netEventPacketCompare(gconstpointer a, gconstpointer b) -{ - Packet* pA, * pB; - - pA= ((NetEvent*) a)->packet; - pB= ((NetEvent*) b)->packet; - - if (netEventPacketEqual(a, b)) - { - return 0; - } - else - { - return 1; - } -} - - -/* - * A GCompareFunc for g_queue_find_custom() - * - * Args: - * a Packet* acked packet - * b Packet* ack packet - * - * Returns: - * 0 if b acks a - */ -static gint packetAckCompare(gconstpointer a, gconstpointer b) -{ - if (isAcking(((Packet*) b), ((Packet*) a))) - { - return 0; - } - else - { - return 1; - } -} - - -/* - * A GCompareFunc for g_queue_find_custom() - * - * Args: - * a: Graph* graph - * b: unsigned int* traceNum - * - * Returns: - * 0 if graph contains traceNum - */ -static gint graphTraceCompare(gconstpointer a, gconstpointer b) -{ - Graph* graph; - unsigned int traceNum; - - graph= (Graph*) a; - traceNum= *(unsigned int *) b; - - if (graph->previousVertex[traceNum] != UINT_MAX) - { - return 0; - } - else if (graph->reference == traceNum) - { - return 0; - } - else - { - return 1; - } -} - - -/* - * A GHashFunc for g_hash_table_new() - * - * 2.4 kernels used tcp_hashfn(), - * - * I've seen something about an XOR hash: - * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14: - * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport); - * h ^= h >> 16; - * h ^= h >> 8; - * return h; - * - * and in 2.6 kernels inet_ehashfn() handles connection hashing with the help of - * Jenkins hashing, jhash.h - * - * This function uses the XOR method. - * - * Args: - * key ConnectionKey* - */ -static guint connectionHash(gconstpointer key) -{ - ConnectionKey* connKey; - guint result; - - connKey= (ConnectionKey*) key; - - result= (connKey->saddr ^ connKey->source) ^ (connKey->daddr ^ connKey->dest); - result^= result >> 16; - result^= result >> 8; - - return result; -} - - -/* - * A GEqualFunc for g_hash_table_new() - * - * Args: - * a, b ConnectionKey* - * - * Returns: - * TRUE if both values are equal - */ -static gboolean connectionEqual(gconstpointer a, gconstpointer b) -{ - ConnectionKey* ckA, * ckB; - - ckA= (ConnectionKey*) a; - ckB= (ConnectionKey*) b; - - // Two packets in the same direction - if (ckA->saddr == ckB->saddr && ckA->daddr == ckB->daddr && ckA->source == - ckB->source && ckA->dest == ckB->dest) - { - return TRUE; - } - // Two packets in opposite directions - else if (ckA->saddr == ckB->daddr && ckA->daddr == ckB->saddr && - ckA->source == ckB->dest && ckA->dest == ckB->source) - { - return TRUE; - } - else - { - return FALSE; - } -} - - -/* - * A GDestroyNotify function for g_hash_table_new_full() - * - * Args: - * data: ConnectionKey* - */ -static void connectionDestroy(gpointer data) -{ - free((ConnectionKey*) data); -} - - -/* - * Convert an IP address from 32 bit form to dotted quad - * - * Args: - * str: A preallocated string of length >= 17 - * addr: Address - */ -static void convertIP(char* const str, const uint32_t addr) -{ - struct in_addr iaddr; - - iaddr.s_addr= htonl(addr); - strcpy(str, inet_ntoa(iaddr)); -} - - -/* - * Print the content of a Packet structure - */ -static void printPacket(const Packet* const packet) -{ - char saddr[17], daddr[17]; - - convertIP(saddr, packet->connKey.saddr); - convertIP(daddr, packet->connKey.daddr); - g_debug("%s:%u to %s:%u tot_len: %u ihl: %u seq: %u ack_seq: %u doff: %u " - "ack: %u rst: %u syn: %u fin: %u", saddr, packet->connKey.source, - daddr, packet->connKey.dest, packet->tot_len, packet->ihl, packet->seq, - packet->ack_seq, packet->doff, packet->ack, packet->rst, packet->syn, - packet->fin); -} - - -/* - * Single-source shortest path search to find the path with the lowest error to - * convert one node's time to another. - * Uses Dijkstra's algorithm - * - * Args: - * fitArray: array with the regression parameters - * traceNum: reference node - * traceNb: number of traces = number of nodes - * distances: array of computed distance from source node to node i, - * INFINITY if i is unreachable, preallocated to the number of - * nodes - * previousVertex: previous vertex from a node i on the way to the source, - * UINT_MAX if i is not on the way or is the source, - * preallocated to the number of nodes - */ -static void shortestPath(Fit* const* const fitArray, const unsigned int - traceNum, const unsigned int traceNb, double* const distances, unsigned - int* const previousVertex) -{ - bool* visited; - unsigned int i, j; - - visited= malloc(traceNb * sizeof(bool)); - - for (i= 0; i < traceNb; i++) - { - const Fit* fit; - - visited[i]= false; - - fit= &fitArray[traceNum][i]; - g_debug("fitArray[traceNum= %u][i= %u]->n = %u\n", traceNum, i, fit->n); - if (fit->n > 0) - { - distances[i]= fit->e; - previousVertex[i]= traceNum; - } - else - { - distances[i]= INFINITY; - previousVertex[i]= UINT_MAX; - } - } - visited[traceNum]= true; - - for (j= 0; j < traceNb; j++) - { - g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); - } - g_debug("\n"); - - for (i= 0; i < traceNb - 2; i++) - { - unsigned int v; - double dvMin; - - dvMin= INFINITY; - for (j= 0; j < traceNb; j++) - { - if (visited[j] == false && distances[j] < dvMin) - { - v= j; - dvMin= distances[j]; - } - } - - g_debug("v= %u dvMin= %g\n", v, dvMin); - - if (dvMin != INFINITY) - { - visited[v]= true; - - for (j= 0; j < traceNb; j++) - { - const Fit* fit; - - fit= &fitArray[v][j]; - if (visited[j] == false && fit->n > 0 && distances[v] + fit->e - < distances[j]) - { - distances[j]= distances[v] + fit->e; - previousVertex[j]= v; - } - } - } - else - { - break; - } - - for (j= 0; j < traceNb; j++) - { - g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); - } - g_debug("\n"); - } - - free(visited); -} - - -/* - * Cummulate the distances between a reference node and the other nodes - * reachable from it in a graph. - * - * Args: - * distances: array of shortest path distances, with UINT_MAX for - * unreachable nodes - * traceNb: number of nodes = number of traces - */ -static double sumDistances(const double* const distances, const unsigned int traceNb) -{ - unsigned int i; - double result; - - result= 0; - for (i= 0; i < traceNb; i++) - { - if (distances[i] != INFINITY) - { - result+= distances[i]; - } - } - - return result; -} - - -/* - * Cummulate the time correction factors between two nodes accross a graph - * - * With traceNum i, reference node r: - * tr= (1 + Xri) * ti + D0ri - * = drift * ti + offset - * - * Args: - * fitArray: array with the regression parameters - * previousVertex: previous vertex from a node i on the way to the source, - * UINT_MAX if i is not on the way or is the source, - * preallocated to the number of nodes - * traceNum: end node, the reference depends on previousVertex - * drift: drift factor - * offset: offset factor - */ -static void factors(Fit* const* const fitArray, const unsigned int* const - previousVertex, const unsigned int traceNum, double* const drift, double* - const offset, double* const stDev) -{ - if (previousVertex[traceNum] == UINT_MAX) - { - *drift= 1.; - *offset= 0.; - *stDev= 0.; - } - else - { - const Fit* fit; - double cummDrift, cummOffset, cummStDev; - unsigned int pv; - - pv= previousVertex[traceNum]; - - fit= &fitArray[pv][traceNum]; - factors(fitArray, previousVertex, pv, &cummDrift, &cummOffset, &cummStDev); - - *drift= cummDrift * (1 + fit->x); - *offset= cummDrift * fit->d0 + cummOffset; - *stDev= fit->x * cummStDev + fit->e; - } -} - - -/* - * Calculate the elapsed time between two timeval values - * - * Args: - * end: end time, result is also stored in this structure - * start: start time - */ -static void timeDiff(struct timeval* const end, const struct timeval* const start) -{ - if (end->tv_usec >= start->tv_usec) - { - end->tv_sec-= start->tv_sec; - end->tv_usec-= start->tv_usec; - } - else - { - end->tv_sec= end->tv_sec - start->tv_sec - 1; - end->tv_usec= end->tv_usec - start->tv_usec + 1e6; - } -} - - -LTTV_MODULE("sync", "Synchronize traces", \ - "Synchronizes a traceset based on the correspondance of network events", \ - init, destroy) diff --git a/lttv/lttv/sync.h b/lttv/lttv/sync.h deleted file mode 100644 index 0581ca69..00000000 --- a/lttv/lttv/sync.h +++ /dev/null @@ -1,183 +0,0 @@ -/* This file is part of the Linux Trace Toolkit viewer - * Copyright (C) 2008 Benjamin Poirier - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License Version 2 as - * published by the Free Software Foundation; - * - * 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., 59 Temple Place - Suite 330, Boston, - * MA 02111-1307, USA. - */ - -#ifndef SYNC_H -#define SYNC_H - -#include -#include -#include -#include - -#include -#include - - -#ifndef g_debug -#define g_debug(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_DEBUG, format) -#endif - -#ifndef g_info -#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) -#endif - - -struct _Packet; - -typedef struct -{ - struct _Packet* packet; - LttTrace* trace; - LttCycleCount tsc; - void* skb; -} NetEvent; - -typedef struct -{ - uint32_t saddr, daddr; - uint16_t source, dest; -} ConnectionKey; - -typedef struct _Packet -{ - ConnectionKey connKey; - unsigned int tot_len, ihl, seq, ack_seq, doff, ack, rst, syn, fin; - NetEvent* inE, * outE; - GQueue* acks; -} Packet; - -typedef struct -{ - unsigned int n; - // notation: s__: sum of __; __2: __ squared; example sd2: sum of d squared - double st, st2, sd, sd2, std, x, d0, e; -} Fit; - -typedef struct -{ - double errorSum; - unsigned int* previousVertex; - unsigned int reference; -} Graph; - -typedef struct -{ - int totRecv, totRecvIp, totInE, totOutE, totPacket, totExchangeEffective, - totExchangeReal; - int totPacketNeedAck, totPacketCummAcked; -} Stats; - -typedef struct -{ - LttvTracesetContext* tsc; - - unsigned int traceNb; - // unsigned int traceNumTable[trace*] - GHashTable* traceNumTable; - - // hookListList conceptually is a two dimensionnal array of LttvTraceHook - // elements. It uses GArrays to interface with other lttv functions that - // do. - GArray* hookListList; - - // inE* pendingRecv[trace] - GHashTable* pendingRecv; - // inE* unMatchedInE[packet] - GHashTable* unMatchedInE; - // outE* unMatchedOutE[packet] - GHashTable* unMatchedOutE; - // packet* unAcked[connKey] - GHashTable* unAcked; - Fit** fitArray; - - GQueue* graphList; - - FILE* dataFd; - Stats* stats; -} SyncState; - -typedef struct -{ - LttvTraceHook* traceHook; - SyncState* syncState; -} HookData; - - -static void init(); -static void destroy(); - -void sync_traceset(LttvTracesetContext* const tsc); - -void registerHooks(SyncState* const syncState); -void unregisterHooks(SyncState* const syncState); -void finalizeLSA(SyncState* const syncState); -void doGraphProcessing(SyncState* const syncState); -void calculateFactors(SyncState* const syncState); - -static gboolean process_event_by_id(void* hook_data, void* call_data); - -static void matchEvents(NetEvent* const netEvent, GHashTable* const unMatchedList, - GHashTable* const unMatchedOppositeList, LttEvent* const event, - LttvTraceHook* const trace_hook, const size_t fieldOffset); - -static bool isAck(const Packet* const packet); -static bool isAcking(const Packet* const ackPacket, const Packet* const - ackedPacket); -static bool needsAck(const Packet* const packet); - -static bool connectionKeyEqual(const ConnectionKey* const a, const - ConnectionKey* const b); - -static void netEventListDestroy(gpointer data); -static void netEventRemove(gpointer data, gpointer user_data); - -static guint netEventPacketHash(gconstpointer key); -static gboolean netEventPacketEqual(gconstpointer a, gconstpointer b); -static void ghtDestroyNetEvent(gpointer data); - -static void packetListDestroy(gpointer data); -static void packetRemove(gpointer data, gpointer user_data); - -static void destroyPacket(Packet* const packet); -static void destroyNetEvent(NetEvent* const event); - -static void graphRemove(gpointer data, gpointer user_data); - -static gint netEventSkbCompare(gconstpointer a, gconstpointer b); -static gint netEventPacketCompare(gconstpointer a, gconstpointer b); -static gint packetAckCompare(gconstpointer a, gconstpointer b); -static gint graphTraceCompare(gconstpointer a, gconstpointer b); - -static guint connectionHash(gconstpointer key); -static gboolean connectionEqual(gconstpointer a, gconstpointer b); -static void connectionDestroy(gpointer data); - -static void convertIP(char* const str, const uint32_t addr); -static void printPacket(const Packet* const packet); - -static void shortestPath(Fit* const* const fitArray, const unsigned int - traceNum, const unsigned int traceNb, double* const distances, unsigned - int* const previousVertex); -static double sumDistances(const double* const distances, const unsigned int traceNb); -static void factors(Fit* const* const fitArray, const unsigned int* const - previousVertex, const unsigned int traceNum, double* const drift, double* - const offset, double* const stDev); - -static void timeDiff(struct timeval* const end, const struct timeval* const start); - -#endif // SYNC_H diff --git a/lttv/lttv/sync/data_structures_tcp.c b/lttv/lttv/sync/data_structures_tcp.c new file mode 100644 index 00000000..0861f341 --- /dev/null +++ b/lttv/lttv/sync/data_structures_tcp.c @@ -0,0 +1,385 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include +#include +#include +#include + +#include "lookup3.h" + +#include "data_structures_tcp.h" + + +#ifndef g_info +#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) +#endif + +// TCP sequence numbers use clock arithmetic, these comparison functions take +// that into account +#define SEQ_LT(a,b) ((int32_t)((a)-(b)) < 0) +#define SEQ_LEQ(a,b) ((int32_t)((a)-(b)) <= 0) +#define SEQ_GT(a,b) ((int32_t)((a)-(b)) > 0) +#define SEQ_GEQ(a,b) ((int32_t)((a)-(b)) >= 0) + + +/* + * Compare two ConnectionKey structures + * + * Returns: + * true if each field of the structure is equal + * false otherwise + */ +bool connectionKeyEqual(const ConnectionKey* const a, const + ConnectionKey* const b) +{ + if (a->saddr == b->saddr && a->daddr == b->daddr && a->source == b->source + && a->dest == b->dest) + { + return true; + } + else + { + return false; + } +} + + +/* + * Check if a packet is an acknowledge of another packet. + * + * Args: + * ackPacket packet that is the confirmation + * ackedPacket packet that contains the original data, both packets have to + * come from the same direction of the same connection + */ +bool isAcking(const Packet* const ackPacket, const Packet* const + ackedPacket) +{ + if (SEQ_GT(ackPacket->inE->packetKey->ack_seq, + ackedPacket->inE->packetKey->seq)) + { + return true; + } + else + { + return false; + } +} + + +/* + * Convert an IP address from 32 bit form to dotted quad + * + * Args: + * str: A preallocated string of length >= 17 + * addr: Address + */ +void convertIP(char* const str, const uint32_t addr) +{ + struct in_addr iaddr; + + iaddr.s_addr= htonl(addr); + strcpy(str, inet_ntoa(iaddr)); +} + + +/* + * Print the content of a Packet structure + */ +void printPacket(const Packet* const packet) +{ + char saddr[17], daddr[17]; + PacketKey* packetKey; + + packetKey= packet->inE->packetKey; + + convertIP(saddr, packetKey->connectionKey.saddr); + convertIP(daddr, packetKey->connectionKey.daddr); + g_debug("%s:%u to %s:%u tot_len: %u ihl: %u seq: %u ack_seq: %u doff: %u " + "ack: %u rst: %u syn: %u fin: %u", saddr, + packetKey->connectionKey.source, daddr, packetKey->connectionKey.dest, + packetKey->tot_len, packetKey->ihl, packetKey->seq, + packetKey->ack_seq, packetKey->doff, packetKey->ack, packetKey->rst, + packetKey->syn, packetKey->fin); +} + + +/* + * A GHashFunc for g_hash_table_new() + * + * This function is for indexing netEvents in unMatched lists. All fields of + * the corresponding packet must match for two keys to be equal. + * + * Args: + * key PacketKey* + */ +guint ghfPacketKeyHash(gconstpointer key) +{ + const PacketKey* p; + uint32_t a, b, c; + + p= (PacketKey*) key; + + a= p->connectionKey.source + (p->connectionKey.dest << 16); + b= p->connectionKey.saddr; + c= p->connectionKey.daddr; + mix(a, b, c); + + a+= p->ihl + (p->tot_len << 8) + (p->doff << 24); + b+= p->seq; + c+= p->ack_seq; + mix(a, b, c); + + a+= p->ack + (p->rst << 8) + (p->syn << 16) + (p->fin << 24); + final(a, b, c); + + return c; +} + + +/* + * A GEqualFunc for g_hash_table_new() + * + * This function is for indexing netEvents in unMatched lists. All fields of + * the corresponding packet must match for two keys to be equal. + * + * Args: + * a, b PacketKey* + * + * Returns: + * TRUE if both values are equal + */ +gboolean gefPacketKeyEqual(gconstpointer a, gconstpointer b) +{ + const PacketKey* pA, * pB; + + pA= ((PacketKey*) a); + pB= ((PacketKey*) b); + + if (connectionKeyEqual(&pA->connectionKey, &pB->connectionKey) && + pA->ihl == pB->ihl && + pA->tot_len == pB->tot_len && + pA->seq == pB->seq && + pA->ack_seq == pB->ack_seq && + pA->doff == pB->doff && + pA->ack == pB->ack && + pA->rst == pB->rst && + pA->syn == pB->syn && + pA->fin == pB->fin) + { + return TRUE; + } + else + { + return FALSE; + } +} + + +/* + * A GDestroyNotify function for g_hash_table_new_full() + * + * Args: + * data: NetEvent* + */ +void gdnDestroyNetEvent(gpointer data) +{ + destroyNetEvent((NetEvent*) data); +} + + +/* + * A GDestroyNotify function for g_hash_table_new_full() + * + * Args: + * data: GQueue* list[Packet] + */ +void gdnPacketListDestroy(gpointer data) +{ + GQueue* list; + + list= (GQueue*) data; + + g_debug("XXXX gdnPacketListDestroy\n"); + + g_queue_foreach(list, &gfPacketDestroy, NULL); + g_queue_free(list); +} + + +/* + * A GFunc for g_queue_foreach() + * + * Args: + * data Packet*, packet to destroy + * user_data NULL + */ +void gfPacketDestroy(gpointer data, gpointer user_data) +{ + g_debug("XXXX gfPacketDestroy\n"); + destroyPacket((Packet*) data); +} + + +/* + * Free the memory used by a Packet and the memory of all its associated + * resources + */ +void destroyPacket(Packet* const packet) +{ + g_debug("XXXX destroyPacket "); + printPacket(packet); + g_debug("\n"); + + g_assert(packet->inE != NULL && packet->outE != NULL && + packet->inE->packetKey == packet->outE->packetKey); + + packet->outE->packetKey= NULL; + + destroyNetEvent(packet->inE); + destroyNetEvent(packet->outE); + + if (packet->acks != NULL) + { + g_queue_foreach(packet->acks, &gfPacketDestroy, NULL); + g_queue_free(packet->acks); + } + + free(packet); +} + + +/* + * Free the memory used by a NetEvent + */ +void destroyNetEvent(NetEvent* const event) +{ + g_debug("XXXX destroyNetEvent\n"); + + if (event->packetKey != NULL) + { + free(event->packetKey); + } + free(event); +} + + +/* + * A GCompareFunc for g_queue_find_custom() + * + * Args: + * a Packet* acked packet + * b Packet* ack packet + * + * Returns: + * 0 if b acks a + */ +gint gcfPacketAckCompare(gconstpointer a, gconstpointer b) +{ + if (isAcking((const Packet*) b, (const Packet*) a)) + { + return 0; + } + else + { + return 1; + } +} + + +/* + * A GHashFunc for g_hash_table_new() + * + * Hash TCP connection keys. Here are a few possible implementations: + * + * 2.4 kernels used tcp_hashfn() + * + * I've seen something about an XOR hash: + * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14: + * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport); + * h ^= h >> 16; + * h ^= h >> 8; + * return h; + * + * In 2.6 kernels, inet_ehashfn() handles connection hashing with the help of + * Jenkins hashing, jhash.h + * + * This function uses jenkins hashing. The hash is not the same for packets in + * opposite directions of the same connection. (Hence the name + * connection*key*hash) + * + * Args: + * key ConnectionKey* + */ +guint ghfConnectionKeyHash(gconstpointer key) +{ + ConnectionKey* connectionKey; + uint32_t a, b, c; + + connectionKey= (ConnectionKey*) key; + + a= connectionKey->source + (connectionKey->dest << 16); + b= connectionKey->saddr; + c= connectionKey->daddr; + final(a, b, c); + + return c; +} + + +/* + * A GEqualFunc for g_hash_table_new() + * + * Args: + * a, b ConnectionKey* + * + * Returns: + * TRUE if both values are equal + */ +gboolean gefConnectionKeyEqual(gconstpointer a, gconstpointer b) +{ + // Two packets in the same direction + if (connectionKeyEqual((const ConnectionKey*) a, (const ConnectionKey*) b)) + { + return TRUE; + } + else + { + return FALSE; + } +} + + +/* + * A GDestroyNotify function for g_hash_table_new_full() + * + * Args: + * data: ConnectionKey* + */ +void gdnConnectionKeyDestroy(gpointer data) +{ + free((ConnectionKey*) data); +} + diff --git a/lttv/lttv/sync/data_structures_tcp.h b/lttv/lttv/sync/data_structures_tcp.h new file mode 100644 index 00000000..0689353d --- /dev/null +++ b/lttv/lttv/sync/data_structures_tcp.h @@ -0,0 +1,106 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef DATA_STRUCTURES_TCP_H +#define DATA_STRUCTURES_TCP_H + +#include +#include +#include + +#include + +typedef struct +{ + uint32_t saddr, daddr; + uint16_t source, dest; +} ConnectionKey; + +typedef struct +{ + ConnectionKey connectionKey; + uint8_t ihl; + uint16_t tot_len; + uint32_t seq, ack_seq; + uint8_t doff; + uint8_t ack, rst, syn, fin; +} PacketKey; + +typedef struct +{ + // lttng metainformation + unsigned long traceNum; + LttCycleCount tsc; + + // kernel metainformation + void* skb; + + // packet header fields + PacketKey* packetKey; +} NetEvent; + +typedef struct +{ + NetEvent* inE, * outE; + GQueue* acks; +} Packet; + +typedef struct +{ + double drift, offset; +} Factors; + +typedef enum +{ + OUT, + IN +} EventType; + + +void convertIP(char* const str, const uint32_t addr); +void printPacket(const Packet* const packet); + +// ConnectionKey-related functions +bool connectionKeyEqual(const ConnectionKey* const a, const ConnectionKey* + const b); + +// NetEvent-related functions +void destroyNetEvent(NetEvent* const event); + +// Packet-related functions +bool isAcking(const Packet* const ackPacket, const Packet* const ackedPacket); +void destroyPacket(Packet* const packet); + +// ConnectionKey-related Glib functions +guint ghfConnectionKeyHash(gconstpointer key); +gboolean gefConnectionKeyEqual(gconstpointer a, gconstpointer b); +void gdnConnectionKeyDestroy(gpointer data); + +// PacketKey-related Glib functions +guint ghfPacketKeyHash(gconstpointer key); +gboolean gefPacketKeyEqual(gconstpointer a, gconstpointer b); + +// NetEvent-related Glib functions +void gdnDestroyNetEvent(gpointer data); + +// Packet-related Glib functions +void gdnPacketListDestroy(gpointer data); +void gfPacketDestroy(gpointer data, gpointer user_data); +gint gcfPacketAckCompare(gconstpointer a, gconstpointer b); + +#endif diff --git a/lttv/lttv/sync/event_analysis.h b/lttv/lttv/sync/event_analysis.h new file mode 100644 index 00000000..3b3cacd5 --- /dev/null +++ b/lttv/lttv/sync/event_analysis.h @@ -0,0 +1,42 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef EVENT_ANALYSIS_H +#define EVENT_ANALYSIS_H + +#include + +#include "data_structures_tcp.h" + + +struct _SyncState; + +typedef struct +{ + char* name; + + void (*initAnalysis)(struct _SyncState* const syncState); + void (*destroyAnalysis)(struct _SyncState* const syncState); + + void (*analyzePacket)(struct _SyncState* const syncState, Packet* const packet); + void (*analyzeExchange)(struct _SyncState* const syncState, Packet* const packet); + GArray* (*finalizeAnalysis)(struct _SyncState* const syncState); + void (*printAnalysisStats)(struct _SyncState* const syncState); +} AnalysisModule; + +#endif diff --git a/lttv/lttv/sync/event_analysis_linreg.c b/lttv/lttv/sync/event_analysis_linreg.c new file mode 100644 index 00000000..8a7bd227 --- /dev/null +++ b/lttv/lttv/sync/event_analysis_linreg.c @@ -0,0 +1,745 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +// for INFINITY in math.h +#define _ISOC99_SOURCE + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include + +#include "sync_chain.h" + +#include "event_analysis_linreg.h" + + +#ifndef g_info +#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) +#endif + + +// Functions common to all analysis modules +static void initAnalysisLinReg(SyncState* const syncState); +static void destroyAnalysisLinReg(SyncState* const syncState); + +static void analyzeExchangeLinReg(SyncState* const syncState, Packet* const packet); +static GArray* finalizeAnalysisLinReg(SyncState* const syncState); +static void printAnalysisStatsLinReg(SyncState* const syncState); + +// Functions specific to this module +static void registerAnalysisLinReg() __attribute__((constructor (101))); + +static void finalizeLSA(SyncState* const syncState); +static void doGraphProcessing(SyncState* const syncState); +static GArray* calculateFactors(SyncState* const syncState); +static void shortestPath(Fit* const* const fitArray, const unsigned int + traceNum, const unsigned int traceNb, double* const distances, + unsigned int* const previousVertex); +static double sumDistances(const double* const distances, const unsigned int + traceNb); +static void reduceFactors(Fit* const* const fitArray, const unsigned int* const + previousVertex, const unsigned int traceNum, double* const drift, + double* const offset, double* const stDev); + +// Graph-related Glib functions +static void gfGraphDestroy(gpointer data, gpointer user_data); +static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b); + + +static AnalysisModule analysisModuleLinReg= { + .name= "linreg", + .initAnalysis= &initAnalysisLinReg, + .destroyAnalysis= &destroyAnalysisLinReg, + .analyzePacket= NULL, + .analyzeExchange= &analyzeExchangeLinReg, + .finalizeAnalysis= &finalizeAnalysisLinReg, + .printAnalysisStats= &printAnalysisStatsLinReg, +}; + + +/* + * Analysis module registering function + */ +static void registerAnalysisLinReg() +{ + g_queue_push_tail(&analysisModules, &analysisModuleLinReg); +} + + +/* + * Analysis init function + * + * This function is called at the beginning of a synchronization run for a set + * of traces. + * + * Allocate some of the analysis specific data structures + * + * Args: + * syncState container for synchronization data. + * This function allocates these analysisData members: + * fitArray + * stDev + */ +static void initAnalysisLinReg(SyncState* const syncState) +{ + unsigned int i; + AnalysisDataLinReg* analysisData; + + analysisData= malloc(sizeof(AnalysisDataLinReg)); + syncState->analysisData= analysisData; + + analysisData->fitArray= malloc(syncState->traceNb * sizeof(Fit*)); + for (i= 0; i < syncState->traceNb; i++) + { + analysisData->fitArray[i]= calloc(syncState->traceNb, sizeof(Fit)); + } + + if (syncState->stats) + { + analysisData->stDev= malloc(sizeof(double) * syncState->traceNb); + } +} + + +/* + * Analysis destroy function + * + * Free the analysis specific data structures + * + * Args: + * syncState container for synchronization data. + * This function deallocates these analysisData members: + * fitArray + * graphList + * stDev + */ +static void destroyAnalysisLinReg(SyncState* const syncState) +{ + unsigned int i; + AnalysisDataLinReg* analysisData; + + analysisData= (AnalysisDataLinReg*) syncState->analysisData; + + if (analysisData == NULL) + { + return; + } + + for (i= 0; i < syncState->traceNb; i++) + { + free(analysisData->fitArray[i]); + } + free(analysisData->fitArray); + + g_queue_foreach(analysisData->graphList, &gfGraphDestroy, NULL); + g_queue_free(analysisData->graphList); + + if (syncState->stats) + { + free(analysisData->stDev); + } + + free(syncState->analysisData); + syncState->analysisData= NULL; +} + + +/* + * Perform analysis on a series of event pairs. + * + * If one event pair is a packet, an exchange is composed of at least two + * packets, one in each direction. There should be a non-negative minimum + * "round trip time" (RTT) between the first and last event of the exchange. + * This RTT should be as small as possible so these packets should be closely + * related in time like a data packet and an acknowledgement packet. If the + * events analyzed are such that the minimum RTT can be zero, there's nothing + * gained in analyzing exchanges beyond what can already be figured out by + * analyzing packets. + * + * An exchange can also consist of more than two packets, in case one packet + * single handedly acknowledges many data packets. + * + * Args: + * syncState container for synchronization data + * packet structure containing the many events + */ +static void analyzeExchangeLinReg(SyncState* const syncState, Packet* const packet) +{ + unsigned int ni, nj; + double dji, eji; + double timoy; + Fit* fit; + Packet* ackedPacket; + AnalysisDataLinReg* analysisData; + + g_debug("Synchronization calculation, "); + g_debug("%d acked packets - using last one, ", + g_queue_get_length(packet->acks)); + + analysisData= (AnalysisDataLinReg*) syncState->analysisData; + ackedPacket= g_queue_peek_tail(packet->acks); + + // Calculate the intermediate values for the + // least-squares analysis + dji= ((double) ackedPacket->inE->tsc - (double) ackedPacket->outE->tsc + + (double) packet->outE->tsc - (double) packet->inE->tsc) / 2; + eji= fabs((double) ackedPacket->inE->tsc - (double) ackedPacket->outE->tsc + - (double) packet->outE->tsc + (double) packet->inE->tsc) / 2; + timoy= ((double) ackedPacket->outE->tsc + (double) packet->inE->tsc) / 2; + ni= ackedPacket->outE->traceNum; + nj= ackedPacket->inE->traceNum; + fit= &analysisData->fitArray[nj][ni]; + + fit->n++; + fit->st+= timoy; + fit->st2+= pow(timoy, 2); + fit->sd+= dji; + fit->sd2+= pow(dji, 2); + fit->std+= timoy * dji; + + g_debug("intermediate values: dji= %f ti moy= %f " + "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f " + "sd2= %f std= %f, ", dji, timoy, ni, nj, fit->n, + fit->st, fit->st2, fit->sd, fit->sd2, fit->std); +} + + +/* + * Finalize the factor calculations + * + * The least squares analysis is finalized and finds the factors directly + * between each pair of traces that had events together. The traces are + * aranged in a graph, a reference trace is chosen and the factors between + * this reference and every other trace is calculated. Sometimes it is + * necessary to use many graphs when there are "islands" of independent + * traces. + * + * Args: + * syncState container for synchronization data. + * + * Returns: + * Factors[traceNb] synchronization factors for each trace + */ +static GArray* finalizeAnalysisLinReg(SyncState* const syncState) +{ + GArray* factors; + + // Finalize the processing + finalizeLSA(syncState); + + // Find a reference node and structure nodes in a graph + doGraphProcessing(syncState); + + /* Calculate the resulting offset and drift between each trace and its + * reference + */ + factors= calculateFactors(syncState); + + return factors; +} + + +/* + * Print statistics related to analysis. Must be called after + * finalizeAnalysis. + * + * Args: + * syncState container for synchronization data. + */ +static void printAnalysisStatsLinReg(SyncState* const syncState) +{ + unsigned int i, j; + AnalysisDataLinReg* analysisData; + + if (!syncState->stats) + { + return; + } + + analysisData= (AnalysisDataLinReg*) syncState->analysisData; + + printf("Linear regression analysis stats:\n"); + + printf("\tIndividual synchronization factors:\n"); + + for (j= 0; j < syncState->traceNb; j++) + { + for (i= 0; i < j; i++) + { + Fit* fit; + + fit= &analysisData->fitArray[j][i]; + printf("\t\t%3d - %-3d: ", i, j); + printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit->d0, fit->x < + 0. ? '-' : '+', fabs(fit->x), fit->e); + + fit= &analysisData->fitArray[i][j]; + printf("\t\t%3d - %-3d: ", j, i); + printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit->d0, fit->x < + 0. ? '-' : '+', fabs(fit->x), fit->e); + } + } + + printf("\tTree:\n"); + for (i= 0; i < syncState->traceNb; i++) + { + GList* result; + + result= g_queue_find_custom(analysisData->graphList, &i, + &gcfGraphTraceCompare); + if (result != NULL) + { + Graph* graph; + + graph= (Graph*) result->data; + + printf("\t\ttrace %u reference %u previous vertex ", i, + graph->reference); + + if (i == graph->reference) + { + printf("- "); + } + else + { + printf("%u ", graph->previousVertex[i]); + } + + printf("stdev= %g\n", analysisData->stDev[i]); + } + else + { + g_error("Trace %d not part of a graph\n", i); + } + } +} + + +/* + * Finalize the least-squares analysis. The intermediate values in the fit + * array are used to calculate the drift and the offset between each pair of + * nodes based on their exchanges. + * + * Args: + * syncState: container for synchronization data. + */ +static void finalizeLSA(SyncState* const syncState) +{ + unsigned int i, j; + AnalysisDataLinReg* analysisData; + + analysisData= (AnalysisDataLinReg*) syncState->analysisData; + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + Fit* fit; + double delta; + + fit= &analysisData->fitArray[i][j]; + + delta= fit->n * fit->st2 - pow(fit->st, 2); + fit->x= (fit->n * fit->std - fit->st * fit->sd) / delta; + fit->d0= (fit->st2 * fit->sd - fit->st * fit->std) / delta; + fit->e= sqrt((fit->sd2 - (fit->n * pow(fit->std, 2) + + pow(fit->sd, 2) * fit->st2 - 2 * fit->st * fit->sd + * fit->std) / delta) / (fit->n - 2)); + + g_debug("[i= %u j= %u]\n", i, j); + g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g\n", + fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std); + g_debug("xij= %g d0ij= %g e= %g\n", fit->x, fit->d0, fit->e); + g_debug("(xji= %g d0ji= %g)\n", -fit->x / (1 + fit->x), + -fit->d0 / (1 + fit->x)); + } + } + } +} + + +/* + * Structure nodes in graphs of nodes that had exchanges. Each graph has a + * reference node, the one that can reach the others with the smallest + * cummulative error. + * + * Args: + * syncState: container for synchronization data. + * This function allocates these analysisData members: + * graphList + */ +static void doGraphProcessing(SyncState* const syncState) +{ + unsigned int i, j; + double* distances; + unsigned int* previousVertex; + AnalysisDataLinReg* analysisData; + + analysisData= (AnalysisDataLinReg*) syncState->analysisData; + + distances= malloc(syncState->traceNb * sizeof(double)); + previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); + analysisData->graphList= g_queue_new(); + + for (i= 0; i < syncState->traceNb; i++) + { + double errorSum; + GList* result; + + // Perform shortest path search + g_debug("shortest path trace %d\ndistances: ", i); + shortestPath(analysisData->fitArray, i, syncState->traceNb, distances, + previousVertex); + + for (j= 0; j < syncState->traceNb; j++) + { + g_debug("%g, ", distances[j]); + } + g_debug("\npreviousVertex: "); + for (j= 0; j < syncState->traceNb; j++) + { + g_debug("%u, ", previousVertex[j]); + } + g_debug("\n"); + + // Group in graphs nodes that have exchanges + errorSum= sumDistances(distances, syncState->traceNb); + result= g_queue_find_custom(analysisData->graphList, &i, + &gcfGraphTraceCompare); + if (result != NULL) + { + Graph* graph; + + g_debug("found graph\n"); + graph= (Graph*) result->data; + if (errorSum < graph->errorSum) + { + g_debug("adding to graph\n"); + graph->errorSum= errorSum; + free(graph->previousVertex); + graph->previousVertex= previousVertex; + graph->reference= i; + previousVertex= malloc(syncState->traceNb * sizeof(unsigned + int)); + } + } + else + { + Graph* newGraph; + + g_debug("creating new graph\n"); + newGraph= malloc(sizeof(Graph)); + newGraph->errorSum= errorSum; + newGraph->previousVertex= previousVertex; + newGraph->reference= i; + previousVertex= malloc(syncState->traceNb * sizeof(unsigned int)); + + g_queue_push_tail(analysisData->graphList, newGraph); + } + } + + free(previousVertex); + free(distances); +} + + +/* + * Calculate the resulting offset and drift between each trace and its + * reference. + * + * Args: + * syncState: container for synchronization data. + * + * Returns: + * Factors[traceNb] synchronization factors for each trace + */ +static GArray* calculateFactors(SyncState* const syncState) +{ + unsigned int i; + AnalysisDataLinReg* analysisData; + GArray* factors; + + analysisData= (AnalysisDataLinReg*) syncState->analysisData; + factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors), + syncState->traceNb); + + // Calculate the resulting offset and drift between each trace and its + // reference + for (i= 0; i < syncState->traceNb; i++) + { + GList* result; + + result= g_queue_find_custom(analysisData->graphList, &i, + &gcfGraphTraceCompare); + if (result != NULL) + { + Graph* graph; + double stDev; + Factors* traceFactors; + + graph= (Graph*) result->data; + traceFactors= &g_array_index(factors, Factors, i); + + reduceFactors(analysisData->fitArray, graph->previousVertex, i, + &traceFactors->drift, &traceFactors->offset, &stDev); + + if (syncState->stats) + { + analysisData->stDev[i]= stDev; + } + } + else + { + g_error("Trace %d not part of a graph\n", i); + } + } + + return factors; +} + + +/* + * Single-source shortest path search to find the path with the lowest error to + * convert one node's time to another. + * Uses Dijkstra's algorithm + * + * Args: + * fitArray: array with the regression parameters + * traceNum: reference node + * traceNb: number of traces = number of nodes + * distances: array of computed distance from source node to node i, + * INFINITY if i is unreachable, preallocated to the number of + * nodes + * previousVertex: previous vertex from a node i on the way to the source, + * UINT_MAX if i is not on the way or is the source, + * preallocated to the number of nodes + */ +static void shortestPath(Fit* const* const fitArray, const unsigned int + traceNum, const unsigned int traceNb, double* const distances, unsigned + int* const previousVertex) +{ + bool* visited; + unsigned int i, j; + + visited= malloc(traceNb * sizeof(bool)); + + for (i= 0; i < traceNb; i++) + { + const Fit* fit; + + visited[i]= false; + + fit= &fitArray[traceNum][i]; + g_debug("fitArray[traceNum= %u][i= %u]->n = %u\n", traceNum, i, fit->n); + if (fit->n > 0) + { + distances[i]= fit->e; + previousVertex[i]= traceNum; + } + else + { + distances[i]= INFINITY; + previousVertex[i]= UINT_MAX; + } + } + visited[traceNum]= true; + + for (j= 0; j < traceNb; j++) + { + g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); + } + g_debug("\n"); + + for (i= 0; i < traceNb - 2; i++) + { + unsigned int v; + double dvMin; + + dvMin= INFINITY; + for (j= 0; j < traceNb; j++) + { + if (visited[j] == false && distances[j] < dvMin) + { + v= j; + dvMin= distances[j]; + } + } + + g_debug("v= %u dvMin= %g\n", v, dvMin); + + if (dvMin != INFINITY) + { + visited[v]= true; + + for (j= 0; j < traceNb; j++) + { + const Fit* fit; + + fit= &fitArray[v][j]; + if (visited[j] == false && fit->n > 0 && distances[v] + fit->e + < distances[j]) + { + distances[j]= distances[v] + fit->e; + previousVertex[j]= v; + } + } + } + else + { + break; + } + + for (j= 0; j < traceNb; j++) + { + g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]); + } + g_debug("\n"); + } + + free(visited); +} + + +/* + * Cummulate the distances between a reference node and the other nodes + * reachable from it in a graph. + * + * Args: + * distances: array of shortest path distances, with UINT_MAX for + * unreachable nodes + * traceNb: number of nodes = number of traces + */ +static double sumDistances(const double* const distances, const unsigned int traceNb) +{ + unsigned int i; + double result; + + result= 0; + for (i= 0; i < traceNb; i++) + { + if (distances[i] != INFINITY) + { + result+= distances[i]; + } + } + + return result; +} + + +/* + * Cummulate the time correction factors between two nodes accross a graph + * + * With traceNum i, reference node r: + * tr= (1 + Xri) * ti + D0ri + * = drift * ti + offset + * + * Args: + * fitArray: array with the regression parameters + * previousVertex: previous vertex from a node i on the way to the source, + * UINT_MAX if i is not on the way or is the source, + * preallocated to the number of nodes + * traceNum: end node, the reference depends on previousVertex + * drift: drift factor + * offset: offset factor + */ +static void reduceFactors(Fit* const* const fitArray, const unsigned int* const + previousVertex, const unsigned int traceNum, double* const drift, double* + const offset, double* const stDev) +{ + if (previousVertex[traceNum] == UINT_MAX) + { + *drift= 1.; + *offset= 0.; + *stDev= 0.; + } + else + { + const Fit* fit; + double cummDrift, cummOffset, cummStDev; + unsigned int pv; + + pv= previousVertex[traceNum]; + + fit= &fitArray[pv][traceNum]; + reduceFactors(fitArray, previousVertex, pv, &cummDrift, &cummOffset, + &cummStDev); + + *drift= cummDrift * (1 + fit->x); + *offset= cummDrift * fit->d0 + cummOffset; + *stDev= fit->x * cummStDev + fit->e; + } +} + + +/* + * A GFunc for g_queue_foreach() + * + * Args: + * data Graph*, graph to destroy + * user_data NULL + */ +static void gfGraphDestroy(gpointer data, gpointer user_data) +{ + Graph* graph; + + graph= (Graph*) data; + + free(graph->previousVertex); + free(graph); +} + + +/* + * A GCompareFunc for g_queue_find_custom() + * + * Args: + * a: Graph* graph + * b: unsigned int* traceNum + * + * Returns: + * 0 if graph contains traceNum + */ +static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b) +{ + Graph* graph; + unsigned int traceNum; + + graph= (Graph*) a; + traceNum= *(unsigned int *) b; + + if (graph->previousVertex[traceNum] != UINT_MAX) + { + return 0; + } + else if (graph->reference == traceNum) + { + return 0; + } + else + { + return 1; + } +} + diff --git a/lttv/lttv/sync/event_analysis_linreg.h b/lttv/lttv/sync/event_analysis_linreg.h new file mode 100644 index 00000000..eb94eaa6 --- /dev/null +++ b/lttv/lttv/sync/event_analysis_linreg.h @@ -0,0 +1,52 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef EVENT_ANALYSIS_LINREG_H +#define EVENT_ANALYSIS_LINREG_H + +#include + +#include "data_structures_tcp.h" + + +typedef struct +{ + unsigned int n; + // notation: s__: sum of __; __2: __ squared; example sd2: sum of d squared + double st, st2, sd, sd2, std, x, d0, e; +} Fit; + +typedef struct +{ + double errorSum; + unsigned int* previousVertex; + unsigned int reference; +} Graph; + +typedef struct +{ + Fit** fitArray; + + // Graph[] + GQueue* graphList; + + // for statistics + double* stDev; +} AnalysisDataLinReg; + +#endif diff --git a/lttv/lttv/sync/event_matching.h b/lttv/lttv/sync/event_matching.h new file mode 100644 index 00000000..f8b4a109 --- /dev/null +++ b/lttv/lttv/sync/event_matching.h @@ -0,0 +1,42 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef EVENT_MATCHING_H +#define EVENT_MATCHING_H + +#include + +#include "data_structures_tcp.h" + + +struct _SyncState; + +typedef struct +{ + char* name; + + void (*initMatching)(struct _SyncState* const syncState); + void (*destroyMatching)(struct _SyncState* const syncState); + + void (*matchEvent)(struct _SyncState* const syncState, NetEvent* const event, + EventType eventType); + GArray* (*finalizeMatching)(struct _SyncState* const syncState); + void (*printMatchingStats)(struct _SyncState* const syncState); +} MatchingModule; + +#endif diff --git a/lttv/lttv/sync/event_matching_tcp.c b/lttv/lttv/sync/event_matching_tcp.c new file mode 100644 index 00000000..892dc7af --- /dev/null +++ b/lttv/lttv/sync/event_matching_tcp.c @@ -0,0 +1,501 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include + +#include "event_analysis.h" +#include "sync_chain.h" + +#include "event_matching_tcp.h" + + +#ifndef g_info +#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) +#endif + + +// Functions common to all matching modules +static void initMatchingTCP(SyncState* const syncState); +static void destroyMatchingTCP(SyncState* const syncState); + +static void matchEventTCP(SyncState* const syncState, NetEvent* const event, + EventType eventType); +static GArray* finalizeMatchingTCP(SyncState* const syncState); +static void printMatchingStatsTCP(SyncState* const syncState); + +// Functions specific to this module +static void registerMatchingTCP() __attribute__((constructor (101))); + +static void matchEvents(SyncState* const syncState, NetEvent* const event, + GHashTable* const unMatchedList, GHashTable* const + unMatchedOppositeList, const size_t fieldOffset, const size_t + oppositeFieldOffset); +static void partialDestroyMatchingTCP(SyncState* const syncState); + +static bool isAck(const Packet* const packet); +static bool needsAck(const Packet* const packet); +static void buildReversedConnectionKey(ConnectionKey* const + reversedConnectionKey, const ConnectionKey* const connectionKey); + + +static MatchingModule matchingModuleTCP = { + .name= "TCP", + .initMatching= &initMatchingTCP, + .destroyMatching= &destroyMatchingTCP, + .matchEvent= &matchEventTCP, + .finalizeMatching= &finalizeMatchingTCP, + .printMatchingStats= &printMatchingStatsTCP, +}; + + +/* + * Matching module registering function + */ +static void registerMatchingTCP() +{ + g_queue_push_tail(&matchingModules, &matchingModuleTCP); +} + + +/* + * Matching init function + * + * This function is called at the beginning of a synchronization run for a set + * of traces. + * + * Allocate the matching specific data structures + * + * Args: + * syncState container for synchronization data. + * This function allocates these matchingData members: + * unMatchedInE + * unMatchedOutE + * unAcked + * stats + */ +static void initMatchingTCP(SyncState* const syncState) +{ + MatchingDataTCP* matchingData; + + matchingData= malloc(sizeof(MatchingDataTCP)); + syncState->matchingData= matchingData; + + matchingData->unMatchedInE= g_hash_table_new_full(&ghfPacketKeyHash, + &gefPacketKeyEqual, NULL, &gdnDestroyNetEvent); + matchingData->unMatchedOutE= g_hash_table_new_full(&ghfPacketKeyHash, + &gefPacketKeyEqual, NULL, &gdnDestroyNetEvent); + matchingData->unAcked= g_hash_table_new_full(&ghfConnectionKeyHash, + &gefConnectionKeyEqual, &gdnConnectionKeyDestroy, + &gdnPacketListDestroy); + + if (syncState->stats) + { + matchingData->stats= calloc(1, sizeof(MatchingStatsTCP)); + } + else + { + matchingData->stats= NULL; + } +} + + +/* + * Matching destroy function + * + * Free the matching specific data structures + * + * Args: + * syncState container for synchronization data. + * This function deallocates these matchingData members: + * stats + */ +static void destroyMatchingTCP(SyncState* const syncState) +{ + MatchingDataTCP* matchingData; + + matchingData= (MatchingDataTCP*) syncState->matchingData; + + if (matchingData == NULL) + { + return; + } + + partialDestroyMatchingTCP(syncState); + + if (syncState->stats) + { + free(matchingData->stats); + } + + free(syncState->matchingData); + syncState->matchingData= NULL; +} + + +/* + * Free some of the matching specific data structures + * + * This function can be called right after the events have been processed to + * free some data structures that are not needed for finalization. + * + * Args: + * syncState container for synchronization data. + * This function deallocates these matchingData members: + * unMatchedInE + * unMatchedOut + * unAcked + */ +static void partialDestroyMatchingTCP(SyncState* const syncState) +{ + MatchingDataTCP* matchingData; + + matchingData= (MatchingDataTCP*) syncState->matchingData; + + if (matchingData == NULL || matchingData->unMatchedInE == NULL) + { + return; + } + + g_debug("Cleaning up unMatchedInE list\n"); + g_hash_table_destroy(matchingData->unMatchedInE); + matchingData->unMatchedInE= NULL; + g_debug("Cleaning up unMatchedOutE list\n"); + g_hash_table_destroy(matchingData->unMatchedOutE); + g_debug("Cleaning up unAcked list\n"); + g_hash_table_destroy(matchingData->unAcked); +} + + +/* + * Try to match one event from a trace with the corresponding event from + * another trace. + * + * Args: + * syncState container for synchronization data. + * event new event to match + * eventType type of event to match + */ +static void matchEventTCP(SyncState* const syncState, NetEvent* const event, EventType eventType) +{ + MatchingDataTCP* matchingData; + + matchingData= (MatchingDataTCP*) syncState->matchingData; + + if (eventType == IN) + { + matchEvents(syncState, event, matchingData->unMatchedInE, + matchingData->unMatchedOutE, offsetof(Packet, inE), + offsetof(Packet, outE)); + } + else + { + matchEvents(syncState, event, matchingData->unMatchedOutE, + matchingData->unMatchedInE, offsetof(Packet, outE), + offsetof(Packet, inE)); + } +} + + +/* + * Call the partial matching destroyer and Obtain the factors from downstream + * + * Args: + * syncState container for synchronization data. + * + * Returns: + * Factors[traceNb] synchronization factors for each trace + */ +static GArray* finalizeMatchingTCP(SyncState* const syncState) +{ + partialDestroyMatchingTCP(syncState); + + return syncState->analysisModule->finalizeAnalysis(syncState); +} + + +/* + * Print statistics related to matching and downstream modules. Must be + * called after finalizeMatching. + * + * Args: + * syncState container for synchronization data. + */ +static void printMatchingStatsTCP(SyncState* const syncState) +{ + MatchingDataTCP* matchingData; + + if (!syncState->stats) + { + return; + } + + matchingData= (MatchingDataTCP*) syncState->matchingData; + + printf("TCP matching stats:\n"); + printf("\ttotal input and output events matched together to form a packet: %d\n", + matchingData->stats->totPacket); + printf("\ttotal packets identified needing an acknowledge: %d\n", + matchingData->stats->totPacketNeedAck); + printf("\ttotal exchanges (four events matched together): %d\n", + matchingData->stats->totExchangeEffective); + printf("\ttotal synchronization exchanges: %d\n", + matchingData->stats->totExchangeSync); + + if (syncState->analysisModule->printAnalysisStats != NULL) + { + syncState->analysisModule->printAnalysisStats(syncState); + } +} + + +/* + * Implementation of a packet matching algorithm for TCP + * + * Args: + * netEvent: new event to match + * unMatchedList: list of unmatched events of the same type (send or + * receive) as netEvent + * unMatchedOppositeList: list of unmatched events of the opposite type of + * netEvent + * fieldOffset: offset of the NetEvent field in the Packet struct for the + * field of the type of netEvent + * oppositeFieldOffset: offset of the NetEvent field in the Packet struct + * for the field of the opposite type of netEvent + */ +static void matchEvents(SyncState* const syncState, NetEvent* const event, + GHashTable* const unMatchedList, GHashTable* const unMatchedOppositeList, + const size_t fieldOffset, const size_t oppositeFieldOffset) +{ + NetEvent* companionEvent; + Packet* packet; + MatchingDataTCP* matchingData; + GQueue* conUnAcked; + + matchingData= (MatchingDataTCP*) syncState->matchingData; + + companionEvent= g_hash_table_lookup(unMatchedOppositeList, event->packetKey); + if (companionEvent != NULL) + { + g_debug("Found matching companion event, "); + + if (syncState->stats) + { + matchingData->stats->totPacket++; + } + + // If it's there, remove it and create a Packet + g_hash_table_steal(unMatchedOppositeList, event->packetKey); + packet= malloc(sizeof(Packet)); + *((NetEvent**) ((void*) packet + fieldOffset))= event; + *((NetEvent**) ((void*) packet + oppositeFieldOffset))= companionEvent; + // Both events can now share the same packetKey + free(packet->outE->packetKey); + packet->outE->packetKey= packet->inE->packetKey; + packet->acks= NULL; + + // Discard loopback traffic + if (packet->inE->traceNum == packet->outE->traceNum) + { + destroyPacket(packet); + return; + } + + if (syncState->analysisModule->analyzePacket) + { + syncState->analysisModule->analyzePacket(syncState, packet); + } + + // We can skip the rest of the algorithm if the analysis module is not + // interested in exchanges + if (!syncState->analysisModule->analyzeExchange) + { + destroyPacket(packet); + return; + } + + // If this packet acknowleges some data ... + if (isAck(packet)) + { + ConnectionKey oppositeConnectionKey; + + buildReversedConnectionKey(&oppositeConnectionKey, + &event->packetKey->connectionKey); + conUnAcked= g_hash_table_lookup(matchingData->unAcked, + &oppositeConnectionKey); + if (conUnAcked != NULL) + { + Packet* ackedPacket; + GList* result; + + result= g_queue_find_custom(conUnAcked, packet, &gcfPacketAckCompare); + + while (result != NULL) + { + // Remove the acknowledged packet from the unAcked list + // and keep it for later offset calculations + g_debug("Found matching unAcked packet, "); + + ackedPacket= (Packet*) result->data; + g_queue_delete_link(conUnAcked, result); + + if (syncState->stats) + { + matchingData->stats->totExchangeEffective++; + } + + if (packet->acks == NULL) + { + packet->acks= g_queue_new(); + } + + g_queue_push_tail(packet->acks, ackedPacket); + + result= g_queue_find_custom(conUnAcked, packet, + &gcfPacketAckCompare); + } + + // It might be possible to do an offset calculation + if (packet->acks != NULL) + { + ackedPacket= g_queue_peek_tail(packet->acks); + if (ackedPacket->outE->traceNum != packet->inE->traceNum + || ackedPacket->inE->traceNum != + packet->outE->traceNum || packet->inE->traceNum == + packet->outE->traceNum) + { + printPacket(ackedPacket); + printPacket(packet); + g_error("Disorganized exchange encountered during " + "synchronization"); + } + else + { + if (syncState->stats) + { + matchingData->stats->totExchangeSync++; + } + + syncState->analysisModule->analyzeExchange(syncState, + packet); + } + } + } + } + + if (needsAck(packet)) + { + if (syncState->stats) + { + matchingData->stats->totPacketNeedAck++; + } + + // If this packet will generate an ack, add it to the unAcked list + g_debug("Adding to unAcked, "); + conUnAcked= g_hash_table_lookup(matchingData->unAcked, + &event->packetKey->connectionKey); + if (conUnAcked == NULL) + { + ConnectionKey* connectionKey; + + connectionKey= malloc(sizeof(ConnectionKey)); + memcpy(connectionKey, &event->packetKey->connectionKey, + sizeof(ConnectionKey)); + g_hash_table_insert(matchingData->unAcked, connectionKey, + conUnAcked= g_queue_new()); + } + g_queue_push_tail(conUnAcked, packet); + } + else + { + destroyPacket(packet); + } + } + else + { + // If there's no corresponding event, add the event to the unmatched + // list for this type of event + g_debug("Adding to unmatched event list, "); + g_hash_table_replace(unMatchedList, event->packetKey, event); + } +} + + +/* + * Check if a packet is an acknowledge + * + * Returns: + * true if it is, + * false otherwise + */ +static bool isAck(const Packet* const packet) +{ + if (packet->inE->packetKey->ack == 1) + { + return true; + } + else + { + return false; + } +} + + +/* + * Check if a packet will increment the sequence number, thus needing an + * acknowledge + * + * Returns: + * true if the packet will need an acknowledge + * false otherwise + */ +static bool needsAck(const Packet* const packet) +{ + if (packet->inE->packetKey->syn || packet->inE->packetKey->fin || + packet->inE->packetKey->tot_len - packet->inE->packetKey->ihl * 4 - + packet->inE->packetKey->doff * 4 > 0) + { + return true; + } + else + { + return false; + } +} + + +/* + * Populate a connection key structure for the opposite direction of a + * connection + * + * Args: + * reversedConnectionKey the result, must be pre-allocated + * connectionKey the connection key to reverse + */ +static void buildReversedConnectionKey(ConnectionKey* const + reversedConnectionKey, const ConnectionKey* const connectionKey) +{ + reversedConnectionKey->saddr= connectionKey->daddr; + reversedConnectionKey->daddr= connectionKey->saddr; + reversedConnectionKey->source= connectionKey->dest; + reversedConnectionKey->dest= connectionKey->source; +} diff --git a/lttv/lttv/sync/event_matching_tcp.h b/lttv/lttv/sync/event_matching_tcp.h new file mode 100644 index 00000000..19da807a --- /dev/null +++ b/lttv/lttv/sync/event_matching_tcp.h @@ -0,0 +1,47 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef EVENT_MATCHING_TCP_H +#define EVENT_MATCHING_TCP_H + +#include + +#include "data_structures_tcp.h" + + +typedef struct +{ + int totPacket, + totPacketNeedAck, + totExchangeEffective, + totExchangeSync; +} MatchingStatsTCP; + +typedef struct +{ + // NetEvent* unMatchedInE[packetKey] + GHashTable* unMatchedInE; + // NetEvent* unMatchedOutE[packetKey] + GHashTable* unMatchedOutE; + // Packet* unAcked[connectionKey] + GHashTable* unAcked; + + MatchingStatsTCP* stats; +} MatchingDataTCP; + +#endif diff --git a/lttv/lttv/sync/event_processing.h b/lttv/lttv/sync/event_processing.h new file mode 100644 index 00000000..bbaae74c --- /dev/null +++ b/lttv/lttv/sync/event_processing.h @@ -0,0 +1,43 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef EVENT_PROCESSING_H +#define EVENT_PROCESSING_H + +#include + +#include + +#include "data_structures_tcp.h" + + +struct _SyncState; + +typedef struct +{ + char* name; + + void (*initProcessing)(struct _SyncState* const syncStateLttv, + LttvTracesetContext* const traceSetContext); + void (*destroyProcessing)(struct _SyncState* const syncState); + + void (*finalizeProcessing)(struct _SyncState* const syncState); + void (*printProcessingStats)(struct _SyncState* const syncState); +} ProcessingModule; + +#endif diff --git a/lttv/lttv/sync/event_processing_lttv_common.c b/lttv/lttv/sync/event_processing_lttv_common.c new file mode 100644 index 00000000..59c7c0f2 --- /dev/null +++ b/lttv/lttv/sync/event_processing_lttv_common.c @@ -0,0 +1,238 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include "event_processing_lttv_common.h" + + +/* This compound literal is #define'd in order to be able to "assign" it and + * 'sizeof()' it + */ +#define EVENT_HOOK_INFO_LIST ((EventHookInfo[]) {\ + {\ + .channelName= LTT_CHANNEL_NET,\ + .eventName= LTT_EVENT_DEV_XMIT,\ + .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_NETWORK_PROTOCOL,\ + LTT_FIELD_TRANSPORT_PROTOCOL, LTT_FIELD_SADDR,\ + LTT_FIELD_DADDR, LTT_FIELD_TOT_LEN, LTT_FIELD_IHL,\ + LTT_FIELD_SOURCE, LTT_FIELD_DEST, LTT_FIELD_SEQ,\ + LTT_FIELD_ACK_SEQ, LTT_FIELD_DOFF, LTT_FIELD_ACK,\ + LTT_FIELD_RST, LTT_FIELD_SYN, LTT_FIELD_FIN),\ + }, {\ + .channelName= LTT_CHANNEL_NET,\ + .eventName= LTT_EVENT_DEV_RECEIVE,\ + .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_PROTOCOL),\ + }, {\ + .channelName= LTT_CHANNEL_NET,\ + .eventName= LTT_EVENT_PKFREE_SKB,\ + .fields= FIELD_ARRAY(LTT_FIELD_SKB),\ + }, {\ + .channelName= LTT_CHANNEL_NET,\ + .eventName= LTT_EVENT_TCPV4_RCV,\ + .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_SADDR,\ + LTT_FIELD_DADDR, LTT_FIELD_TOT_LEN, LTT_FIELD_IHL,\ + LTT_FIELD_SOURCE, LTT_FIELD_DEST, LTT_FIELD_SEQ,\ + LTT_FIELD_ACK_SEQ, LTT_FIELD_DOFF, LTT_FIELD_ACK,\ + LTT_FIELD_RST, LTT_FIELD_SYN, LTT_FIELD_FIN),\ + }, {\ + .channelName= LTT_CHANNEL_NETIF_STATE,\ + .eventName= LTT_EVENT_NETWORK_IPV4_INTERFACE,\ + .fields= FIELD_ARRAY(LTT_FIELD_NAME, LTT_FIELD_ADDRESS,\ + LTT_FIELD_UP),\ + }\ +}) + +#ifndef g_info +#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) +#endif + + +typedef struct +{ + GQuark channelName; + GQuark eventName; + GQuark* fields; +} EventHookInfo; + + +/* + * Initialize the GQuarks needed to register the event hooks for + * synchronization + */ +void createQuarks() +{ + LTT_CHANNEL_NET= g_quark_from_static_string("net"); + LTT_CHANNEL_NETIF_STATE= g_quark_from_static_string("netif_state"); + + LTT_EVENT_DEV_XMIT= g_quark_from_static_string("dev_xmit"); + LTT_EVENT_DEV_RECEIVE= g_quark_from_static_string("dev_receive"); + LTT_EVENT_PKFREE_SKB= g_quark_from_static_string("pkfree_skb"); + LTT_EVENT_TCPV4_RCV= g_quark_from_static_string("tcpv4_rcv"); + LTT_EVENT_NETWORK_IPV4_INTERFACE= + g_quark_from_static_string("network_ipv4_interface"); + + LTT_FIELD_SKB= g_quark_from_static_string("skb"); + LTT_FIELD_PROTOCOL= g_quark_from_static_string("protocol"); + LTT_FIELD_NETWORK_PROTOCOL= + g_quark_from_static_string("network_protocol"); + LTT_FIELD_TRANSPORT_PROTOCOL= + g_quark_from_static_string("transport_protocol"); + LTT_FIELD_SADDR= g_quark_from_static_string("saddr"); + LTT_FIELD_DADDR= g_quark_from_static_string("daddr"); + LTT_FIELD_TOT_LEN= g_quark_from_static_string("tot_len"); + LTT_FIELD_IHL= g_quark_from_static_string("ihl"); + LTT_FIELD_SOURCE= g_quark_from_static_string("source"); + LTT_FIELD_DEST= g_quark_from_static_string("dest"); + LTT_FIELD_SEQ= g_quark_from_static_string("seq"); + LTT_FIELD_ACK_SEQ= g_quark_from_static_string("ack_seq"); + LTT_FIELD_DOFF= g_quark_from_static_string("doff"); + LTT_FIELD_ACK= g_quark_from_static_string("ack"); + LTT_FIELD_RST= g_quark_from_static_string("rst"); + LTT_FIELD_SYN= g_quark_from_static_string("syn"); + LTT_FIELD_FIN= g_quark_from_static_string("fin"); + LTT_FIELD_NAME= g_quark_from_static_string("name"); + LTT_FIELD_ADDRESS= g_quark_from_static_string("address"); + LTT_FIELD_UP= g_quark_from_static_string("up"); +} + + +/* Fill hookListList and add event hooks + * + * Note: possibilité de remettre le code avec lttv_trace_find_marker_ids (voir + * r328) + * + * Args: + */ +void registerHooks(GArray* hookListList, LttvTracesetContext* const + traceSetContext, unsigned int traceNb, LttvHook hookFunction, gpointer + hookData) +{ + unsigned int i, j, k; + unsigned int hookNb; + EventHookInfo* eventHookInfoList; + + eventHookInfoList= EVENT_HOOK_INFO_LIST; + hookNb= sizeof(EVENT_HOOK_INFO_LIST) / sizeof(EventHookInfo); + + for(i= 0; i < traceNb; i++) + { + LttvTraceContext* tc; + GArray* hookList; + int retval; + + tc= traceSetContext->traces[i]; + hookList= g_array_new(FALSE, FALSE, sizeof(LttvTraceHook)); + g_array_append_val(hookListList, hookList); + + // Find the hooks + for (j= 0; j < hookNb; j++) + { + guint old_len; + + old_len= hookList->len; + retval= lttv_trace_find_hook(tc->t, + eventHookInfoList[j].channelName, + eventHookInfoList[j].eventName, eventHookInfoList[j].fields, + hookFunction, hookData, &hookList); + if (retval != 0) + { + g_warning("Trace %d contains no %s.%s marker\n", i, + g_quark_to_string(eventHookInfoList[j].channelName), + g_quark_to_string(eventHookInfoList[j].eventName)); + } + else + { + g_assert(hookList->len - old_len == 1); + } + } + + // Add the hooks to each tracefile's event_by_id hook list + for(j= 0; j < tc->tracefiles->len; j++) + { + LttvTracefileContext* tfc; + + tfc= g_array_index(tc->tracefiles, LttvTracefileContext*, j); + + for(k= 0; k < hookList->len; k++) + { + LttvTraceHook* traceHook; + + traceHook= &g_array_index(hookList, LttvTraceHook, k); + if (traceHook->hook_data != hookData) + { + g_assert_not_reached(); + } + if (traceHook->mdata == tfc->tf->mdata) + { + lttv_hooks_add(lttv_hooks_by_id_find( tfc->event_by_id, + traceHook->id), traceHook->h, traceHook, + LTTV_PRIO_DEFAULT); + } + } + } + } +} + + +/* Remove event hooks and free hookListList + * + * Args: + * hookListList: LttvTraceHook hookListList[traceNum][hookNum] + * traceSetContext: LTTV traceset + * traceNb: number of traces in the traceset + */ +void unregisterHooks(GArray* hookListList, LttvTracesetContext* const + traceSetContext, unsigned int traceNb) +{ + unsigned int i, j, k; + + for(i= 0; i < traceNb; i++) + { + LttvTraceContext* tc; + GArray* hookList; + + tc= traceSetContext->traces[i]; + hookList= g_array_index(hookListList, GArray*, i); + + // Remove the hooks from each tracefile's event_by_id hook list + for(j= 0; j < tc->tracefiles->len; j++) + { + LttvTracefileContext* tfc; + + tfc= g_array_index(tc->tracefiles, LttvTracefileContext*, j); + + for(k= 0; k < hookList->len; k++) + { + LttvTraceHook* traceHook; + + traceHook= &g_array_index(hookList, LttvTraceHook, k); + if (traceHook->mdata == tfc->tf->mdata) + { + lttv_hooks_remove_data(lttv_hooks_by_id_find(tfc->event_by_id, + traceHook->id), traceHook->h, traceHook); + } + } + } + + g_array_free(hookList, TRUE); + } + g_array_free(hookListList, TRUE); +} diff --git a/lttv/lttv/sync/event_processing_lttv_common.h b/lttv/lttv/sync/event_processing_lttv_common.h new file mode 100644 index 00000000..de57a650 --- /dev/null +++ b/lttv/lttv/sync/event_processing_lttv_common.h @@ -0,0 +1,68 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef EVENT_PROCESSING_LTTV_COMMON_H +#define EVENT_PROCESSING_LTTV_COMMON_H + +#include + +#include + + +GQuark + LTT_CHANNEL_NET, + LTT_CHANNEL_NETIF_STATE; + +GQuark + LTT_EVENT_DEV_XMIT, + LTT_EVENT_DEV_RECEIVE, + LTT_EVENT_PKFREE_SKB, + LTT_EVENT_TCPV4_RCV, + LTT_EVENT_NETWORK_IPV4_INTERFACE; + +GQuark + LTT_FIELD_SKB, + LTT_FIELD_PROTOCOL, + LTT_FIELD_NETWORK_PROTOCOL, + LTT_FIELD_TRANSPORT_PROTOCOL, + LTT_FIELD_SADDR, + LTT_FIELD_DADDR, + LTT_FIELD_TOT_LEN, + LTT_FIELD_IHL, + LTT_FIELD_SOURCE, + LTT_FIELD_DEST, + LTT_FIELD_SEQ, + LTT_FIELD_ACK_SEQ, + LTT_FIELD_DOFF, + LTT_FIELD_ACK, + LTT_FIELD_RST, + LTT_FIELD_SYN, + LTT_FIELD_FIN, + LTT_FIELD_NAME, + LTT_FIELD_ADDRESS, + LTT_FIELD_UP; + + +void createQuarks(); +void registerHooks(GArray* hookListList, LttvTracesetContext* const + traceSetContext, unsigned int traceNb, LttvHook hookFunction, gpointer + hookData); +void unregisterHooks(GArray* hookListList, LttvTracesetContext* const + traceSetContext, unsigned int traceNb); + +#endif diff --git a/lttv/lttv/sync/event_processing_lttv_null.c b/lttv/lttv/sync/event_processing_lttv_null.c new file mode 100644 index 00000000..2229bc10 --- /dev/null +++ b/lttv/lttv/sync/event_processing_lttv_null.c @@ -0,0 +1,149 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include + +#include "sync_chain.h" +#include "event_processing_lttv_common.h" + +#include "event_processing_lttv_null.h" + + +#ifndef g_info +#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) +#endif + + +// Functions common to all matching modules +static void initProcessingLTTVNull(SyncState* const syncState, + LttvTracesetContext* const traceSetContext); +static void destroyProcessingLTTVNull(SyncState* const syncState); + +static void finalizeProcessingLTTVNull(SyncState* const syncState); + +// Functions specific to this module +static void registerProcessingLTTVNull() __attribute__((constructor (102))); +static gboolean processEventLTTVNull(void* hookData, void* callData); + + +static ProcessingModule processingModuleLTTVNull = { + .name= "LTTV-null", + .initProcessing= &initProcessingLTTVNull, + .destroyProcessing= &destroyProcessingLTTVNull, + .finalizeProcessing= &finalizeProcessingLTTVNull, + .printProcessingStats= NULL, +}; + + + +/* + * Processing Module registering function + */ +static void registerProcessingLTTVNull() +{ + g_queue_push_tail(&processingModules, &processingModuleLTTVNull); + + createQuarks(); +} + + +/* + * Allocate and initialize data structures for synchronizing a traceset. + * Register event hooks. + * + * Args: + * syncState: container for synchronization data. + * This function allocates these processingData members: + * hookListList + * traceSetContext: set of LTTV traces + */ +static void initProcessingLTTVNull(SyncState* const syncState, + LttvTracesetContext* const traceSetContext) +{ + ProcessingDataLTTVNull* processingData; + + processingData= malloc(sizeof(ProcessingDataLTTVNull)); + syncState->processingData= processingData; + processingData->traceSetContext= traceSetContext; + + processingData->hookListList= g_array_sized_new(FALSE, FALSE, + sizeof(GArray*), syncState->traceNb); + + registerHooks(processingData->hookListList, traceSetContext, + syncState->traceNb, &processEventLTTVNull, syncState); +} + + +/* + * Nothing to do + * + * Args: + * syncState container for synchronization data. + */ +static void finalizeProcessingLTTVNull(SyncState* const syncState) +{ + return; +} + + +/* + * Unregister event hooks. Deallocate processingData. + * + * Args: + * syncState: container for synchronization data. + * This function deallocates these members: + * hookListList + */ +static void destroyProcessingLTTVNull(SyncState* const syncState) +{ + ProcessingDataLTTVNull* processingData; + + processingData= (ProcessingDataLTTVNull*) syncState->processingData; + + if (processingData == NULL) + { + return; + } + + unregisterHooks(processingData->hookListList, + processingData->traceSetContext, syncState->traceNb); + + free(syncState->processingData); + syncState->processingData= NULL; +} + + +/* + * Lttv hook function that will be called for network events + * + * Args: + * hookData: LttvTraceHook* for the type of event that generated the call + * callData: LttvTracefileContext* at the moment of the event + * + * Returns: + * FALSE Always returns FALSE, meaning to keep processing hooks for + * this event + */ +static gboolean processEventLTTVNull(void* hookData, void* callData) +{ + return FALSE; +} diff --git a/lttv/lttv/sync/event_processing_lttv_null.h b/lttv/lttv/sync/event_processing_lttv_null.h new file mode 100644 index 00000000..090b6b8f --- /dev/null +++ b/lttv/lttv/sync/event_processing_lttv_null.h @@ -0,0 +1,38 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef EVENT_PROCESSING_LTTV_NULL_H +#define EVENT_PROCESSING_LTTV_NULL_H + +#include + +#include + + +typedef struct +{ + LttvTracesetContext* traceSetContext; + + // hookListList conceptually is a two dimensionnal array of LttvTraceHook + // elements. It uses GArrays to interface with other lttv functions that + // do. + // LttvTraceHook hookListList[traceNum][hookNum] + GArray* hookListList; +} ProcessingDataLTTVNull; + +#endif diff --git a/lttv/lttv/sync/event_processing_lttv_standard.c b/lttv/lttv/sync/event_processing_lttv_standard.c new file mode 100644 index 00000000..cef9f2b9 --- /dev/null +++ b/lttv/lttv/sync/event_processing_lttv_standard.c @@ -0,0 +1,582 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#define _ISOC99_SOURCE + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include +#include +#include + +#include "sync_chain.h" +#include "event_processing_lttv_common.h" + +#include "event_processing_lttv_standard.h" + + +#ifndef g_info +#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) +#endif + + +// Functions common to all matching modules +static void initProcessingLTTVStandard(SyncState* const syncState, + LttvTracesetContext* const traceSetContext); +static void destroyProcessingLTTVStandard(SyncState* const syncState); + +static void finalizeProcessingLTTVStandard(SyncState* const syncState); +static void printProcessingStatsLTTVStandard(SyncState* const syncState); + +// Functions specific to this module +static void registerProcessingLTTVStandard() __attribute__((constructor (102))); +static gboolean processEventLTTVStandard(void* hookData, void* callData); +static void partialDestroyProcessingLTTVStandard(SyncState* const syncState); + + +static ProcessingModule processingModuleLTTVStandard = { + .name= "LTTV-standard", + .initProcessing= &initProcessingLTTVStandard, + .destroyProcessing= &destroyProcessingLTTVStandard, + .finalizeProcessing= &finalizeProcessingLTTVStandard, + .printProcessingStats= &printProcessingStatsLTTVStandard, +}; + + + +/* + * Processing Module registering function + */ +static void registerProcessingLTTVStandard() +{ + g_queue_push_tail(&processingModules, &processingModuleLTTVStandard); + + createQuarks(); +} + + +/* + * Allocate and initialize data structures for synchronizing a traceset. + * Register event hooks. + * + * Args: + * syncState: container for synchronization data. + * This function allocates these processingData members: + * traceNumTable + * pendingRecv + * hookListList + * stats + * traceSetContext: set of LTTV traces + */ +static void initProcessingLTTVStandard(SyncState* const syncState, LttvTracesetContext* + const traceSetContext) +{ + unsigned int i; + ProcessingDataLTTVStandard* processingData; + + processingData= malloc(sizeof(ProcessingDataLTTVStandard)); + syncState->processingData= processingData; + processingData->traceSetContext= traceSetContext; + + if (syncState->stats) + { + processingData->stats= calloc(1, sizeof(ProcessingStatsLTTVStandard)); + } + else + { + processingData->stats= NULL; + } + + processingData->traceNumTable= g_hash_table_new(&g_direct_hash, NULL); + processingData->hookListList= g_array_sized_new(FALSE, FALSE, + sizeof(GArray*), syncState->traceNb); + processingData->pendingRecv= malloc(sizeof(GHashTable*) * + syncState->traceNb); + + for(i= 0; i < syncState->traceNb; i++) + { + g_hash_table_insert(processingData->traceNumTable, + processingData->traceSetContext->traces[i]->t, (gpointer) i); + } + + for(i= 0; i < syncState->traceNb; i++) + { + processingData->pendingRecv[i]= g_hash_table_new_full(&g_direct_hash, + NULL, NULL, &gdnDestroyNetEvent); + } + + registerHooks(processingData->hookListList, traceSetContext, + syncState->traceNb, &processEventLTTVStandard, syncState); +} + + +/* + * Call the partial processing destroyer, obtain and adjust the factors from + * downstream + * + * Args: + * syncState container for synchronization data. + */ +static void finalizeProcessingLTTVStandard(SyncState* const syncState) +{ + unsigned int i; + GArray* factors; + double minOffset, minDrift; + unsigned int refFreqTrace; + ProcessingDataLTTVStandard* processingData; + + processingData= (ProcessingDataLTTVStandard*) syncState->processingData; + + partialDestroyProcessingLTTVStandard(syncState); + + factors= syncState->matchingModule->finalizeMatching(syncState); + + /* The offsets are adjusted so the lowest one is 0. This is done because + * of a Lttv specific limitation: events cannot have negative times. By + * having non-negative offsets, events cannot be moved backwards to + * negative times. + */ + minOffset= 0; + for (i= 0; i < syncState->traceNb; i++) + { + minOffset= MIN(g_array_index(factors, Factors, i).offset, minOffset); + } + + for (i= 0; i < syncState->traceNb; i++) + { + g_array_index(factors, Factors, i).offset-= minOffset; + } + + /* Because the timestamps are corrected at the TSC level (not at the + * LttTime level) all trace frequencies must be made equal. We choose to + * use the frequency of the system with the lowest drift + */ + minDrift= INFINITY; + refFreqTrace= 0; + for (i= 0; i < syncState->traceNb; i++) + { + if (g_array_index(factors, Factors, i).drift < minDrift) + { + minDrift= g_array_index(factors, Factors, i).drift; + refFreqTrace= i; + } + } + g_assert(syncState->traceNb == 0 || minDrift != INFINITY); + + // Write the factors to the LttTrace structures + for (i= 0; i < syncState->traceNb; i++) + { + LttTrace* t; + Factors* traceFactors; + + t= processingData->traceSetContext->traces[i]->t; + traceFactors= &g_array_index(factors, Factors, i); + + t->drift= traceFactors->drift; + t->offset= traceFactors->offset; + t->start_freq= + processingData->traceSetContext->traces[refFreqTrace]->t->start_freq; + t->freq_scale= + processingData->traceSetContext->traces[refFreqTrace]->t->freq_scale; + t->start_time_from_tsc = + ltt_time_from_uint64(tsc_to_uint64(t->freq_scale, t->start_freq, + t->drift * t->start_tsc + t->offset)); + } + + g_array_free(factors, TRUE); + + lttv_traceset_context_compute_time_span(processingData->traceSetContext, + &processingData->traceSetContext->time_span); + + g_debug("traceset start %ld.%09ld end %ld.%09ld\n", + processingData->traceSetContext->time_span.start_time.tv_sec, + processingData->traceSetContext->time_span.start_time.tv_nsec, + processingData->traceSetContext->time_span.end_time.tv_sec, + processingData->traceSetContext->time_span.end_time.tv_nsec); + + return; +} + + +/* + * Print statistics related to processing and downstream modules. Must be + * called after finalizeProcessing. + * + * Args: + * syncState container for synchronization data. + */ +static void printProcessingStatsLTTVStandard(SyncState* const syncState) +{ + unsigned int i; + ProcessingDataLTTVStandard* processingData; + + if (!syncState->stats) + { + return; + } + + processingData= (ProcessingDataLTTVStandard*) syncState->processingData; + + printf("LTTV processing stats:\n"); + printf("\treceived frames: %d\n", processingData->stats->totRecv); + printf("\treceived frames that are IP: %d\n", + processingData->stats->totRecvIp); + printf("\treceived and processed packets that are TCP: %d\n", + processingData->stats->totInE); + printf("\tsent packets that are TCP: %d\n", + processingData->stats->totOutE); + + if (syncState->matchingModule->printMatchingStats != NULL) + { + syncState->matchingModule->printMatchingStats(syncState); + } + + printf("Resulting synchronization factors:\n"); + for (i= 0; i < syncState->traceNb; i++) + { + LttTrace* t; + + t= processingData->traceSetContext->traces[i]->t; + + printf("\ttrace %u drift= %g offset= %g (%f) start time= %ld.%09ld\n", + i, t->drift, t->offset, (double) tsc_to_uint64(t->freq_scale, + t->start_freq, t->offset) / NANOSECONDS_PER_SECOND, + t->start_time_from_tsc.tv_sec, t->start_time_from_tsc.tv_nsec); + } +} + + +/* + * Unregister event hooks. Deallocate processingData. + * + * Args: + * syncState: container for synchronization data. + * This function deallocates these processingData members: + * stats + */ +static void destroyProcessingLTTVStandard(SyncState* const syncState) +{ + ProcessingDataLTTVStandard* processingData; + + processingData= (ProcessingDataLTTVStandard*) syncState->processingData; + + if (processingData == NULL) + { + return; + } + + partialDestroyProcessingLTTVStandard(syncState); + + if (syncState->stats) + { + free(processingData->stats); + } + + free(syncState->processingData); + syncState->processingData= NULL; +} + + +/* + * Unregister event hooks. Deallocate some of processingData. + * + * This function can be called right after the events have been processed to + * free some data structures that are not needed for finalization. + * + * Args: + * syncState: container for synchronization data. + * This function deallocates these members: + * traceNumTable + * hookListList + * pendingRecv + */ +static void partialDestroyProcessingLTTVStandard(SyncState* const syncState) +{ + unsigned int i; + ProcessingDataLTTVStandard* processingData; + + processingData= (ProcessingDataLTTVStandard*) syncState->processingData; + + if (processingData == NULL || processingData->traceNumTable == NULL) + { + return; + } + + g_hash_table_destroy(processingData->traceNumTable); + processingData->traceNumTable= NULL; + + for(i= 0; i < syncState->traceNb; i++) + { + + g_debug("Cleaning up pendingRecv list\n"); + g_hash_table_destroy(processingData->pendingRecv[i]); + } + free(processingData->pendingRecv); + + unregisterHooks(processingData->hookListList, + processingData->traceSetContext, syncState->traceNb); +} + + +/* + * Lttv hook function that will be called for network events + * + * Args: + * hookData: LttvTraceHook* for the type of event that generated the call + * callData: LttvTracefileContext* at the moment of the event + * + * Returns: + * FALSE Always returns FALSE, meaning to keep processing hooks for + * this event + */ +static gboolean processEventLTTVStandard(void* hookData, void* callData) +{ + LttvTraceHook* traceHook; + LttvTracefileContext* tfc; + LttEvent* event; + LttTime time; + LttCycleCount tsc; + LttTrace* trace; + unsigned long traceNum; + struct marker_info* info; + SyncState* syncState; + ProcessingDataLTTVStandard* processingData; + + traceHook= (LttvTraceHook*) hookData; + tfc= (LttvTracefileContext*) callData; + syncState= (SyncState*) traceHook->hook_data; + processingData= (ProcessingDataLTTVStandard*) syncState->processingData; + event= ltt_tracefile_get_event(tfc->tf); + time= ltt_event_time(event); + tsc= ltt_event_cycle_count(event); + trace= tfc->t_context->t; + info= marker_get_info_from_id(tfc->tf->mdata, event->event_id); + + g_assert(g_hash_table_lookup_extended(processingData->traceNumTable, + trace, NULL, (gpointer*) &traceNum)); + + g_debug("XXXX process event: time: %ld.%09ld trace: %ld (%p) name: %s ", + (long) time.tv_sec, time.tv_nsec, traceNum, trace, + g_quark_to_string(info->name)); + + if (info->name == LTT_EVENT_DEV_XMIT) + { + NetEvent* outE; + + if (!ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 1)) == ETH_P_IP || + !ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 2)) == IPPROTO_TCP) + { + return FALSE; + } + + if (syncState->stats) + { + processingData->stats->totOutE++; + } + + outE= malloc(sizeof(NetEvent)); + outE->packetKey= malloc(sizeof(PacketKey)); + + outE->traceNum= traceNum; + outE->tsc= tsc; + outE->skb= NULL; + outE->packetKey->connectionKey.saddr= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 3)); + outE->packetKey->connectionKey.daddr= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 4)); + outE->packetKey->tot_len= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 5)); + outE->packetKey->ihl= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 6)); + outE->packetKey->connectionKey.source= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 7)); + outE->packetKey->connectionKey.dest= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 8)); + outE->packetKey->seq= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 9)); + outE->packetKey->ack_seq= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 10)); + outE->packetKey->doff= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 11)); + outE->packetKey->ack= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 12)); + outE->packetKey->rst= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 13)); + outE->packetKey->syn= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 14)); + outE->packetKey->fin= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 15)); + + syncState->matchingModule->matchEvent(syncState, outE, OUT); + + g_debug("Output event done\n"); + } + else if (info->name == LTT_EVENT_DEV_RECEIVE) + { + guint32 protocol; + + if (syncState->stats) + { + processingData->stats->totRecv++; + } + + protocol= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 1)); + + if (protocol == ETH_P_IP) + { + NetEvent* inE; + + if (syncState->stats) + { + processingData->stats->totRecvIp++; + } + + inE= malloc(sizeof(NetEvent)); + + inE->traceNum= traceNum; + inE->tsc= tsc; + inE->skb= (void*) (long) ltt_event_get_long_unsigned(event, + lttv_trace_get_hook_field(traceHook, 0)); + inE->packetKey= NULL; + + g_hash_table_insert(processingData->pendingRecv[traceNum], + inE->skb, inE); + + g_debug("Adding inE %p for skb %p to pendingRecv\n", inE, inE->skb); + } + else + { + g_debug("\n"); + } + } + else if (info->name == LTT_EVENT_TCPV4_RCV) + { + NetEvent* inE; + void* skb; + + // Search pendingRecv for an event with the same skb + skb= (void*) (long) ltt_event_get_long_unsigned(event, + lttv_trace_get_hook_field(traceHook, 0)); + + inE= (NetEvent*) + g_hash_table_lookup(processingData->pendingRecv[traceNum], skb); + if (inE == NULL) + { + // This should only happen in case of lost events + g_debug("No matching pending receive event found\n"); + } + else + { + if (syncState->stats) + { + processingData->stats->totInE++; + } + + // If it's there, remove it and proceed with a receive event + g_hash_table_steal(processingData->pendingRecv[traceNum], skb); + + inE->packetKey= malloc(sizeof(PacketKey)); + + inE->packetKey->connectionKey.saddr= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 1)); + inE->packetKey->connectionKey.daddr= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 2)); + inE->packetKey->tot_len= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 3)); + inE->packetKey->ihl= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 4)); + inE->packetKey->connectionKey.source= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 5)); + inE->packetKey->connectionKey.dest= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 6)); + inE->packetKey->seq= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 7)); + inE->packetKey->ack_seq= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 8)); + inE->packetKey->doff= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 9)); + inE->packetKey->ack= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 10)); + inE->packetKey->rst= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 11)); + inE->packetKey->syn= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 12)); + inE->packetKey->fin= ltt_event_get_unsigned(event, + lttv_trace_get_hook_field(traceHook, 13)); + + syncState->matchingModule->matchEvent(syncState, inE, IN); + + g_debug("Input event %p for skb %p done\n", inE, skb); + } + } + else if (info->name == LTT_EVENT_PKFREE_SKB) + { + gboolean result; + void* skb; + + // Search pendingRecv for an event with the same skb + skb= (void*) (long) ltt_event_get_long_unsigned(event, + lttv_trace_get_hook_field(traceHook, 0)); + + result= g_hash_table_remove(processingData->pendingRecv[traceNum], + skb); + if (result == FALSE) + { + g_debug("No matching pending receive event found, \"shaddow" + "skb\" %p\n", skb); + } + else + { + g_debug("Non-TCP skb %p\n", skb); + } + } + else if (info->name == LTT_EVENT_NETWORK_IPV4_INTERFACE) + { + char* name; + guint64 address; + gint64 up; + char addressString[17]; + + address= ltt_event_get_long_unsigned(event, + lttv_trace_get_hook_field(traceHook, 1)); + up= ltt_event_get_long_int(event, lttv_trace_get_hook_field(traceHook, + 2)); + /* name must be the last field to get or else copy the string, see the + * doc for ltt_event_get_string() + */ + name= ltt_event_get_string(event, lttv_trace_get_hook_field(traceHook, + 0)); + + convertIP(addressString, address); + + g_debug("name \"%s\" address %s up %lld\n", name, addressString, up); + } + else + { + g_assert_not_reached(); + } + + return FALSE; +} diff --git a/lttv/lttv/sync/event_processing_lttv_standard.h b/lttv/lttv/sync/event_processing_lttv_standard.h new file mode 100644 index 00000000..15139ec6 --- /dev/null +++ b/lttv/lttv/sync/event_processing_lttv_standard.h @@ -0,0 +1,55 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef EVENT_PROCESSING_LTTV_STANDARD_H +#define EVENT_PROCESSING_LTTV_STANDARD_H + +#include + +#include + +#include "event_processing.h" + +typedef struct +{ + int totRecv, + totRecvIp, + totInE, + totOutE; +} ProcessingStatsLTTVStandard; + +typedef struct +{ + LttvTracesetContext* traceSetContext; + + // unsigned int traceNumTable[trace*] + GHashTable* traceNumTable; + + // hookListList conceptually is a two dimensionnal array of LttvTraceHook + // elements. It uses GArrays to interface with other lttv functions that + // do. + // LttvTraceHook hookListList[traceNum][hookNum] + GArray* hookListList; + + // inE* pendingRecv[traceNb] + GHashTable** pendingRecv; + + ProcessingStatsLTTVStandard* stats; +} ProcessingDataLTTVStandard; + +#endif diff --git a/lttv/lttv/lookup3.h b/lttv/lttv/sync/lookup3.h similarity index 100% rename from lttv/lttv/lookup3.h rename to lttv/lttv/sync/lookup3.h diff --git a/lttv/lttv/sync/sync_chain.c b/lttv/lttv/sync/sync_chain.c new file mode 100644 index 00000000..210be504 --- /dev/null +++ b/lttv/lttv/sync/sync_chain.c @@ -0,0 +1,329 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include + +#include +#include + +#include "sync_chain.h" + + +#ifndef g_info +#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) +#endif + + +static void init(); +static void destroy(); + +static void timeDiff(struct timeval* const end, const struct timeval* const start); +static gint gcfCompareAnalysis(gconstpointer a, gconstpointer b); +static gint gcfCompareProcessing(gconstpointer a, gconstpointer b); +static void gfAppendAnalysisName(gpointer data, gpointer user_data); + +static gboolean optionSync; +static gboolean optionSyncStats; +static gboolean optionSyncNull; +static char* optionSyncAnalysis; + +GQueue processingModules= G_QUEUE_INIT; +GQueue matchingModules= G_QUEUE_INIT; +GQueue analysisModules= G_QUEUE_INIT; + + +/* + * Module init function + * + * This function is declared to be the module initialization function. Event + * modules are registered with a "constructor (102)" attribute except one in + * each class (processing, matching, analysis) which is chosen to be the + * default and which is registered with a "constructor (101)" attribute. + * Constructors with no priority are called after constructors with + * priorities. The result is that the list of event modules is known when this + * function is executed. + */ +static void init() +{ + GString* analysisModulesNames; + + g_debug("\t\t\tXXXX sync init\n"); + + optionSync= FALSE; + lttv_option_add("sync", '\0', "synchronize the time between the traces" , + "none", LTTV_OPT_NONE, &optionSync, NULL, NULL); + + optionSyncStats= FALSE; + lttv_option_add("sync-stats", '\0', "print statistics about the time " + "synchronization", "none", LTTV_OPT_NONE, &optionSyncStats, NULL, + NULL); + + optionSyncNull= FALSE; + lttv_option_add("sync-null", '\0', "read the events but do not perform " + "any processing", "none", LTTV_OPT_NONE, &optionSyncNull, NULL, NULL); + + g_assert(g_queue_get_length(&analysisModules) > 0); + optionSyncAnalysis= ((AnalysisModule*) + g_queue_peek_head(&analysisModules))->name; + analysisModulesNames= g_string_new(""); + g_queue_foreach(&analysisModules, &gfAppendAnalysisName, + analysisModulesNames); + // remove the last ", " + g_string_truncate(analysisModulesNames, analysisModulesNames->len - 2); + lttv_option_add("sync-analysis", '\0', "specify the algorithm to use for " + "event analysis" , analysisModulesNames->str, LTTV_OPT_STRING, + &optionSyncAnalysis, NULL, NULL); + g_string_free(analysisModulesNames, TRUE); +} + + +/* + * Module unload function + */ +static void destroy() +{ + g_debug("\t\t\tXXXX sync destroy\n"); + + lttv_option_remove("sync"); + lttv_option_remove("sync-stats"); + lttv_option_remove("sync-null"); + lttv_option_remove("sync-analysis"); +} + + +/* + * Calculate a traceset's drift and offset values based on network events + * + * The individual correction factors are written out to each trace. + * + * Args: + * traceSetContext: traceset + */ +void syncTraceset(LttvTracesetContext* const traceSetContext) +{ + SyncState* syncState; + struct timeval startTime, endTime; + struct rusage startUsage, endUsage; + GList* result; + int retval; + + if (optionSync == FALSE) + { + g_debug("Not synchronizing traceset because option is disabled"); + return; + } + + if (optionSyncStats) + { + gettimeofday(&startTime, 0); + getrusage(RUSAGE_SELF, &startUsage); + } + + // Initialize data structures + syncState= malloc(sizeof(SyncState)); + syncState->traceNb= lttv_traceset_number(traceSetContext->ts); + + if (optionSyncStats) + { + syncState->stats= true; + } + else + { + syncState->stats= false; + } + + syncState->processingData= NULL; + if (optionSyncNull) + { + result= g_queue_find_custom(&processingModules, "LTTV-null", + &gcfCompareProcessing); + } + else + { + result= g_queue_find_custom(&processingModules, "LTTV-standard", + &gcfCompareProcessing); + } + g_assert(result != NULL); + syncState->processingModule= (ProcessingModule*) result->data; + syncState->processingModule->initProcessing(syncState, traceSetContext); + + syncState->matchingData= NULL; + syncState->analysisData= NULL; + if (optionSyncNull) + { + syncState->matchingModule= NULL; + syncState->analysisModule= NULL; + } + else + { + g_assert(g_queue_get_length(&matchingModules) == 1); + syncState->matchingModule= (MatchingModule*) + g_queue_peek_head(&matchingModules); + syncState->matchingModule->initMatching(syncState); + + result= g_queue_find_custom(&analysisModules, optionSyncAnalysis, + &gcfCompareAnalysis); + if (result != NULL) + { + syncState->analysisModule= (AnalysisModule*) result->data; + syncState->analysisModule->initAnalysis(syncState); + } + else + { + g_error("Analysis module '%s' not found", optionSyncAnalysis); + } + } + + // Process traceset + lttv_process_traceset_seek_time(traceSetContext, ltt_time_zero); + lttv_process_traceset_middle(traceSetContext, ltt_time_infinite, + G_MAXULONG, NULL); + lttv_process_traceset_seek_time(traceSetContext, ltt_time_zero); + + syncState->processingModule->finalizeProcessing(syncState); + + if (syncState->processingModule->printProcessingStats != NULL) + { + syncState->processingModule->printProcessingStats(syncState); + } + + syncState->processingModule->destroyProcessing(syncState); + if (syncState->matchingModule != NULL) + { + syncState->matchingModule->destroyMatching(syncState); + } + if (syncState->analysisModule != NULL) + { + syncState->analysisModule->destroyAnalysis(syncState); + } + + free(syncState); + + if (optionSyncStats) + { + gettimeofday(&endTime, 0); + retval= getrusage(RUSAGE_SELF, &endUsage); + + timeDiff(&endTime, &startTime); + timeDiff(&endUsage.ru_utime, &startUsage.ru_utime); + timeDiff(&endUsage.ru_stime, &startUsage.ru_stime); + + printf("Synchronization time:\n"); + printf("\treal time: %ld.%06ld\n", endTime.tv_sec, endTime.tv_usec); + printf("\tuser time: %ld.%06ld\n", endUsage.ru_utime.tv_sec, + endUsage.ru_utime.tv_usec); + printf("\tsystem time: %ld.%06ld\n", endUsage.ru_stime.tv_sec, + endUsage.ru_stime.tv_usec); + } +} + + +/* + * Calculate the elapsed time between two timeval values + * + * Args: + * end: end time, result is also stored in this structure + * start: start time + */ +static void timeDiff(struct timeval* const end, const struct timeval* const start) +{ + if (end->tv_usec >= start->tv_usec) + { + end->tv_sec-= start->tv_sec; + end->tv_usec-= start->tv_usec; + } + else + { + end->tv_sec= end->tv_sec - start->tv_sec - 1; + end->tv_usec= end->tv_usec - start->tv_usec + 1e6; + } +} + + +/* + * A GCompareFunc for g_slist_find_custom() + * + * Args: + * a: AnalysisModule*, element's data + * b: char*, user data to compare against + * + * Returns: + * 0 if the analysis module a's name is b + */ +static gint gcfCompareAnalysis(gconstpointer a, gconstpointer b) +{ + const AnalysisModule* analysisModule; + const char* name; + + analysisModule= (const AnalysisModule*)a; + name= (const char*)b; + + return strncmp(analysisModule->name, name, strlen(analysisModule->name) + + 1); +} + + +/* + * A GCompareFunc for g_slist_find_custom() + * + * Args: + * a: ProcessingModule*, element's data + * b: char*, user data to compare against + * + * Returns: + * 0 if the analysis module a's name is b + */ +static gint gcfCompareProcessing(gconstpointer a, gconstpointer b) +{ + const ProcessingModule* processingModule; + const char* name; + + processingModule= (const ProcessingModule*)a; + name= (const char*)b; + + return strncmp(processingModule->name, name, + strlen(processingModule->name) + 1); +} + + +/* + * A GFunc for g_queue_foreach() + * + * Concatenate analysis module names. + * + * Args: + * data: AnalysisModule* + * user_data: GString*, concatenated names + */ +static void gfAppendAnalysisName(gpointer data, gpointer user_data) +{ + g_string_append((GString*) user_data, ((AnalysisModule*) data)->name); + g_string_append((GString*) user_data, ", "); +} + + +LTTV_MODULE("sync", "Synchronize traces", \ + "Synchronizes a traceset based on the correspondance of network events", \ + init, destroy, "option") + diff --git a/lttv/lttv/sync/sync_chain.h b/lttv/lttv/sync/sync_chain.h new file mode 100644 index 00000000..9515c6e5 --- /dev/null +++ b/lttv/lttv/sync/sync_chain.h @@ -0,0 +1,48 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 Benjamin Poirier + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License Version 2 as + * published by the Free Software Foundation; + * + * 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., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +#ifndef SYNC_CHAIN_H +#define SYNC_CHAIN_H + +#include + +#include "event_processing.h" +#include "event_matching.h" +#include "event_analysis.h" + +typedef struct _SyncState +{ + unsigned int traceNb; + bool stats; + + const ProcessingModule* processingModule; + void* processingData; + const MatchingModule* matchingModule; + void* matchingData; + const AnalysisModule* analysisModule; + void* analysisData; +} SyncState; + +extern GQueue processingModules; +extern GQueue matchingModules; +extern GQueue analysisModules; + + +void syncTraceset(LttvTracesetContext* const traceSetContext); + +#endif diff --git a/lttv/modules/gui/lttvwindow/lttvwindow/callbacks.c b/lttv/modules/gui/lttvwindow/lttvwindow/callbacks.c index 5ce1f925..53681f48 100644 --- a/lttv/modules/gui/lttvwindow/lttvwindow/callbacks.c +++ b/lttv/modules/gui/lttvwindow/lttvwindow/callbacks.c @@ -39,6 +39,7 @@ #include #include #include +#include #include #include #include @@ -468,7 +469,7 @@ int SetTraceset(Tab * tab, LttvTraceset *traceset) LttvTracesetContext *tsc = LTTV_TRACESET_CONTEXT(tab->traceset_info->traceset_context); - sync_traceset(tsc); + syncTraceset(tsc); TimeInterval time_span = tsc->time_span; TimeWindow new_time_window = tab->time_window; LttTime new_current_time = tab->current_time; diff --git a/lttv/modules/text/batchAnalysis.c b/lttv/modules/text/batchAnalysis.c index ca3a92ef..3ee4d021 100644 --- a/lttv/modules/text/batchAnalysis.c +++ b/lttv/modules/text/batchAnalysis.c @@ -34,6 +34,7 @@ #include #include #include +#include static LttvTraceset *traceset; @@ -90,7 +91,7 @@ static gboolean process_traceset(void *hook_data, void *call_data) lttv_context_init(tc, traceset); - sync_traceset(tc); + syncTraceset(tc); lttv_state_add_event_hooks(tc); if(a_stats) lttv_stats_add_event_hooks(tscs); -- 2.34.1