From f10c27a850e57bf88bf1d4440eb450729782f409 Mon Sep 17 00:00:00 2001 From: Benjamin Poirier Date: Tue, 27 Oct 2009 17:08:28 -0400 Subject: [PATCH] Add a broadcast matching module Matches UDP packets based on their first 8 bytes of content (this also depends on the kernel instrumentation). Signed-off-by: Benjamin Poirier --- lttv/lttv/Makefile.am | 1 + lttv/lttv/sync/Makefile.am | 1 + lttv/lttv/sync/data_structures.h | 32 ++- lttv/lttv/sync/event_matching_broadcast.c | 315 ++++++++++++++++++++++ lttv/lttv/sync/event_matching_broadcast.h | 43 +++ lttv/lttv/sync/sync_chain_lttv.c | 6 +- lttv/modules/text/sync_chain_batch.c | 2 +- 7 files changed, 383 insertions(+), 17 deletions(-) create mode 100644 lttv/lttv/sync/event_matching_broadcast.c create mode 100644 lttv/lttv/sync/event_matching_broadcast.h diff --git a/lttv/lttv/Makefile.am b/lttv/lttv/Makefile.am index 3738b812..b758b434 100644 --- a/lttv/lttv/Makefile.am +++ b/lttv/lttv/Makefile.am @@ -60,6 +60,7 @@ lttv_real_SOURCES = \ sync/event_processing_lttng_common.c\ sync/event_processing_lttng_standard.c\ sync/event_processing_lttng_null.c\ + sync/event_matching_broadcast.c\ sync/event_matching_tcp.c\ sync/event_analysis_linreg.c\ sync/event_analysis_chull.c diff --git a/lttv/lttv/sync/Makefile.am b/lttv/lttv/sync/Makefile.am index dbe9ed59..5c7ead0a 100644 --- a/lttv/lttv/sync/Makefile.am +++ b/lttv/lttv/sync/Makefile.am @@ -6,6 +6,7 @@ check_PROGRAMS = unittest unittest_SOURCES = \ unittest.c\ data_structures.c\ + event_matching_broadcast.c\ event_matching_tcp.c\ event_analysis_linreg.c\ event_analysis_chull.c diff --git a/lttv/lttv/sync/data_structures.h b/lttv/lttv/sync/data_structures.h index 765967ff..62a776a8 100644 --- a/lttv/lttv/sync/data_structures.h +++ b/lttv/lttv/sync/data_structures.h @@ -25,6 +25,20 @@ #include + +enum Direction +{ + OUT, + IN, +}; + +enum EventType +{ + TCP, + UDP, + TYPE_COUNT, // This must be the last field +}; + // Stage 1 to 2: These structures are passed from processing to matching modules // TCP events typedef struct @@ -43,19 +57,6 @@ typedef struct uint8_t ack, rst, syn, fin; } SegmentKey; -enum Direction -{ - OUT, - IN, -}; - -enum EventType -{ - TCP, - UDP, - TYPE_COUNT, -}; - typedef struct { enum Direction direction; @@ -134,6 +135,11 @@ void gdnConnectionKeyDestroy(gpointer data); guint ghfSegmentKeyHash(gconstpointer key); gboolean gefSegmentKeyEqual(gconstpointer a, gconstpointer b); +// DatagramKey-related functions +guint ghfDatagramKeyHash(gconstpointer key); +gboolean gefDatagramKeyEqual(gconstpointer a, gconstpointer b); +void gdnDestroyDatagramKey(gpointer data); + // Event-related functions void gdnDestroyEvent(gpointer data); void destroyEvent(Event* const event); diff --git a/lttv/lttv/sync/event_matching_broadcast.c b/lttv/lttv/sync/event_matching_broadcast.c new file mode 100644 index 00000000..9eb6e108 --- /dev/null +++ b/lttv/lttv/sync/event_matching_broadcast.c @@ -0,0 +1,315 @@ +/* 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 "event_analysis.h" +#include "sync_chain_lttv.h" + +#include "event_matching_broadcast.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 initMatchingBroadcast(SyncState* const syncState); +static void destroyMatchingBroadcast(SyncState* const syncState); + +static void matchEventBroadcast(SyncState* const syncState, Event* const event); +static GArray* finalizeMatchingBroadcast(SyncState* const syncState); +static void printMatchingStatsBroadcast(SyncState* const syncState); + +// Functions specific to this module +static void registerMatchingBroadcast() __attribute__((constructor (101))); + +static void partialDestroyMatchingBroadcast(SyncState* const syncState); + +static MatchingModule matchingModuleBroadcast = { + .name= "broadcast", + .canMatch[TCP]= false, + .canMatch[UDP]= true, + .initMatching= &initMatchingBroadcast, + .destroyMatching= &destroyMatchingBroadcast, + .matchEvent= &matchEventBroadcast, + .finalizeMatching= &finalizeMatchingBroadcast, + .printMatchingStats= &printMatchingStatsBroadcast, + .writeMatchingGraphsPlots= NULL, + .writeMatchingGraphsOptions= NULL, +}; + + +/* + * Matching module registering function + */ +static void registerMatchingBroadcast() +{ + g_queue_push_tail(&matchingModules, &matchingModuleBroadcast); +} + + +/* + * 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: + * pendingBroadcasts + * stats + */ +static void initMatchingBroadcast(SyncState* const syncState) +{ + MatchingDataBroadcast* matchingData; + + matchingData= malloc(sizeof(MatchingDataBroadcast)); + syncState->matchingData= matchingData; + + matchingData->pendingBroadcasts= g_hash_table_new_full(&ghfDatagramKeyHash, + &gefDatagramKeyEqual, &gdnDestroyDatagramKey, &gdnDestroyBroadcast); + + if (syncState->stats) + { + matchingData->stats= calloc(1, sizeof(MatchingStatsBroadcast)); + } + 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 destroyMatchingBroadcast(SyncState* const syncState) +{ + MatchingDataBroadcast* matchingData; + + matchingData= (MatchingDataBroadcast*) syncState->matchingData; + + if (matchingData == NULL) + { + return; + } + + partialDestroyMatchingBroadcast(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: + * pendingBroadcasts + */ +static void partialDestroyMatchingBroadcast(SyncState* const syncState) +{ + MatchingDataBroadcast* matchingData; + + matchingData= (MatchingDataBroadcast*) syncState->matchingData; + + if (matchingData == NULL || matchingData->pendingBroadcasts == NULL) + { + return; + } + + g_hash_table_destroy(matchingData->pendingBroadcasts); + matchingData->pendingBroadcasts= NULL; +} + + +/* + * Try to match one broadcast with previously received broadcasts (based on + * the addresses and the fist bytes of data they contain). Deliver them to the + * analysis module once a traceNb events have been accumulated for a + * broadcast. + * + * Args: + * syncState container for synchronization data. + * event new event to match + */ +static void matchEventBroadcast(SyncState* const syncState, Event* const event) +{ + MatchingDataBroadcast* matchingData; + + g_assert(event->type == UDP); + + matchingData= (MatchingDataBroadcast*) syncState->matchingData; + + if (!event->event.udpEvent->unicast) + { + if (event->event.udpEvent->direction == IN) + { + Broadcast* broadcast; + DatagramKey* datagramKey; + gboolean result; + + if (matchingData->stats) + { + matchingData->stats->totReceive++; + } + + // s'il est déjà dans pendingBroadcasts + // l'ajouter à son broadcast + // s'il y a traceNb éléments + // le retirer de pending et le livrer à analysis + // détruire le broadcast (et ses éléments) + // sinon + // créer un broadcast et l'ajouter à pending + + result= + g_hash_table_lookup_extended(matchingData->pendingBroadcasts, + event->event.udpEvent->datagramKey, (gpointer) + &datagramKey, (gpointer) &broadcast); + if (result) + { + g_queue_push_tail(broadcast->events, event); + if (broadcast->events->length == syncState->traceNb) + { + g_hash_table_steal(matchingData->pendingBroadcasts, datagramKey); + free(datagramKey); + syncState->analysisModule->analyzeBroadcast(syncState, broadcast); + destroyBroadcast(broadcast); + } + } + else + { + broadcast= malloc(sizeof(Broadcast)); + broadcast->events= g_queue_new(); + g_queue_push_tail(broadcast->events, event); + } + } + else + { + if (matchingData->stats) + { + matchingData->stats->totTransmit++; + } + + event->destroy(event); + } + } + else + { + event->destroy(event); + } + +} + + +/* + * 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* finalizeMatchingBroadcast(SyncState* const syncState) +{ + MatchingDataBroadcast* matchingData; + + matchingData= (MatchingDataBroadcast*) syncState->matchingData; + + if (matchingData->stats) + { + matchingData->stats->totIncomplete= + g_hash_table_size(matchingData->pendingBroadcasts); + } + + partialDestroyMatchingBroadcast(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 printMatchingStatsBroadcast(SyncState* const syncState) +{ + MatchingDataBroadcast* matchingData; + + if (!syncState->stats) + { + return; + } + + matchingData= (MatchingDataBroadcast*) syncState->matchingData; + + printf("Broadcast matching stats:\n"); + printf("\ttotal broadcasts datagrams emitted: %u\n", + matchingData->stats->totTransmit); + printf("\ttotal broadcasts datagrams received: %u\n", + matchingData->stats->totReceive); + printf("\ttotal broadcast groups for which all emissions were identified: %u\n", + matchingData->stats->totComplete); + printf("\ttotal broadcast groups missing some emissions: %u\n", + matchingData->stats->totIncomplete); + if (matchingData->stats->totIncomplete > 0) + { + printf("\taverage number of broadcast datagrams received in incomplete groups: %f\n", + (double) (matchingData->stats->totReceive - + matchingData->stats->totComplete * syncState->traceNb) / + matchingData->stats->totIncomplete); + } + + if (syncState->analysisModule->printAnalysisStats != NULL) + { + syncState->analysisModule->printAnalysisStats(syncState); + } +} diff --git a/lttv/lttv/sync/event_matching_broadcast.h b/lttv/lttv/sync/event_matching_broadcast.h new file mode 100644 index 00000000..3492f0a7 --- /dev/null +++ b/lttv/lttv/sync/event_matching_broadcast.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_MATCHING_BROADCAST_H +#define EVENT_MATCHING_BROADCAST_H + +#include + +#include "data_structures.h" + + +typedef struct +{ + unsigned int totComplete, + totReceive, + totIncomplete, + totTransmit; +} MatchingStatsBroadcast; + +typedef struct +{ + // Broadcast* pendingBroadcasts[dataStart] + GHashTable* pendingBroadcasts; + + MatchingStatsBroadcast* stats; +} MatchingDataBroadcast; + +#endif diff --git a/lttv/lttv/sync/sync_chain_lttv.c b/lttv/lttv/sync/sync_chain_lttv.c index 2003e95f..399b7962 100644 --- a/lttv/lttv/sync/sync_chain_lttv.c +++ b/lttv/lttv/sync/sync_chain_lttv.c @@ -233,9 +233,9 @@ void syncTraceset(LttvTracesetContext* const traceSetContext) } // Identify matching and analysis modules - g_assert(g_queue_get_length(&matchingModules) == 1); - syncState->matchingModule= (MatchingModule*) - g_queue_peek_head(&matchingModules); + result= g_queue_find_custom(&matchingModules, "TCP", &gcfCompareMatching); + g_assert(result != NULL); + syncState->matchingModule= (MatchingModule*) result->data; result= g_queue_find_custom(&analysisModules, optionSyncAnalysis, &gcfCompareAnalysis); diff --git a/lttv/modules/text/sync_chain_batch.c b/lttv/modules/text/sync_chain_batch.c index 376a696a..3a4bc0df 100644 --- a/lttv/modules/text/sync_chain_batch.c +++ b/lttv/modules/text/sync_chain_batch.c @@ -339,7 +339,7 @@ void setupSyncChain(LttvTracesetContext* const traceSetContext) } syncState->matchingData= NULL; - result= g_queue_find_custom(&matchingModules, "TCP", &gcfCompareMatching); + result= g_queue_find_custom(&matchingModules, "broadcast", &gcfCompareMatching); syncState->matchingModule= (MatchingModule*) result->data; syncState->analysisData= NULL; -- 2.34.1