--- /dev/null
+/* This file is part of the Linux Trace Toolkit viewer
+ * Copyright (C) 2008 Benjamin Poirier <benjamin.poirier@polymtl.ca>
+ * 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 <config.h>
+#endif
+
+#include <arpa/inet.h>
+#include <fcntl.h>
+#include <glib.h>
+#include <limits.h>
+#include <linux/if_ether.h>
+#include <math.h>
+#include <netinet/in.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/resource.h>
+#include <sys/socket.h>
+#include <sys/stat.h>
+#include <sys/time.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <lttv/module.h>
+#include <lttv/option.h>
+
+#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("<default>\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)
projects / lttv.git / blobdiff