projects / lttv.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Text mode clock synchronization
[lttv.git] / lttv / lttv / sync.c
1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2008 Benjamin Poirier <benjamin.poirier@polymtl.ca>
3 * This program is free software; you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License Version 2 as
5 * published by the Free Software Foundation;
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software
14 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
15 * MA 02111-1307, USA.
16 */
17
18 // for INFINITY in math.h
19 #define _ISOC99_SOURCE
20
21 #ifdef HAVE_CONFIG_H
22 #include <config.h>
23 #endif
24
25 #include <arpa/inet.h>
26 #include <fcntl.h>
27 #include <glib.h>
28 #include <limits.h>
29 #include <linux/if_ether.h>
30 #include <math.h>
31 #include <netinet/in.h>
32 #include <stdint.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <sys/resource.h>
36 #include <sys/socket.h>
37 #include <sys/stat.h>
38 #include <sys/time.h>
39 #include <sys/types.h>
40 #include <unistd.h>
41
42 #include <lttv/module.h>
43 #include <lttv/option.h>
44
45 #include "lookup3.h"
46
47 #include "sync.h"
48
49
50 GQuark
51 LTT_CHANNEL_NET,
52 LTT_CHANNEL_NETIF_STATE;
53
54 GQuark
55 LTT_EVENT_DEV_HARD_START_XMIT_TCP,
56 LTT_EVENT_DEV_RECEIVE,
57 LTT_EVENT_PKFREE_SKB,
58 LTT_EVENT_TCPV4_RCV,
59 LTT_EVENT_NETWORK_IPV4_INTERFACE;
60
61 GQuark
62 LTT_FIELD_SKB,
63 LTT_FIELD_PROTOCOL,
64 LTT_FIELD_SADDR,
65 LTT_FIELD_DADDR,
66 LTT_FIELD_TOT_LEN,
67 LTT_FIELD_IHL,
68 LTT_FIELD_SOURCE,
69 LTT_FIELD_DEST,
70 LTT_FIELD_SEQ,
71 LTT_FIELD_ACK_SEQ,
72 LTT_FIELD_DOFF,
73 LTT_FIELD_ACK,
74 LTT_FIELD_RST,
75 LTT_FIELD_SYN,
76 LTT_FIELD_FIN,
77 LTT_FIELD_NAME,
78 LTT_FIELD_ADDRESS,
79 LTT_FIELD_UP;
80
81 static gboolean optionSync;
82 static gboolean optionSyncStats;
83 static char* optionSyncData;
84
85 /*
86 * Module init function
87 */
88 static void init()
89 {
90 g_debug("\t\t\tXXXX sync init\n");
91
92 LTT_CHANNEL_NET= g_quark_from_string("net");
93 LTT_CHANNEL_NETIF_STATE= g_quark_from_string("netif_state");
94
95 LTT_EVENT_DEV_HARD_START_XMIT_TCP=
96 g_quark_from_string("dev_hard_start_xmit_tcp");
97 LTT_EVENT_DEV_RECEIVE= g_quark_from_string("dev_receive");
98 LTT_EVENT_PKFREE_SKB= g_quark_from_string("pkfree_skb");
99 LTT_EVENT_TCPV4_RCV= g_quark_from_string("tcpv4_rcv");
100 LTT_EVENT_NETWORK_IPV4_INTERFACE=
101 g_quark_from_string("network_ipv4_interface");
102
103 LTT_FIELD_SKB= g_quark_from_string("skb");
104 LTT_FIELD_PROTOCOL= g_quark_from_string("protocol");
105 LTT_FIELD_SADDR= g_quark_from_string("saddr");
106 LTT_FIELD_DADDR= g_quark_from_string("daddr");
107 LTT_FIELD_TOT_LEN= g_quark_from_string("tot_len");
108 LTT_FIELD_IHL= g_quark_from_string("ihl");
109 LTT_FIELD_SOURCE= g_quark_from_string("source");
110 LTT_FIELD_DEST= g_quark_from_string("dest");
111 LTT_FIELD_SEQ= g_quark_from_string("seq");
112 LTT_FIELD_ACK_SEQ= g_quark_from_string("ack_seq");
113 LTT_FIELD_DOFF= g_quark_from_string("doff");
114 LTT_FIELD_ACK= g_quark_from_string("ack");
115 LTT_FIELD_RST= g_quark_from_string("rst");
116 LTT_FIELD_SYN= g_quark_from_string("syn");
117 LTT_FIELD_FIN= g_quark_from_string("fin");
118 LTT_FIELD_NAME= g_quark_from_string("name");
119 LTT_FIELD_ADDRESS= g_quark_from_string("address");
120 LTT_FIELD_UP= g_quark_from_string("up");
121
122 optionSync= FALSE;
123 lttv_option_add("sync", '\0', "synchronize the time between tracefiles "
124 "based on network communications", "none", LTTV_OPT_NONE, &optionSync,
125 NULL, NULL);
126
127 optionSyncStats= FALSE;
128 lttv_option_add("sync-stats", '\0', "print statistics about the time "
129 "synchronization", "none", LTTV_OPT_NONE, &optionSyncStats, NULL, NULL);
130
131 optionSyncData= NULL;
132 lttv_option_add("sync-data", '\0', "save information about every offset "
133 "identified", "pathname of the file where to save the offsets",
134 LTTV_OPT_STRING, &optionSyncData, NULL, NULL);
135 }
136
137
138 /*
139 * Module unload function
140 */
141 static void destroy()
142 {
143 g_debug("\t\t\tXXXX sync destroy\n");
144
145 lttv_option_remove("sync");
146 lttv_option_remove("sync-stats");
147 lttv_option_remove("sync-data");
148 }
149
150
151 /*
152 * Calculate a traceset's drift and offset values based on network events
153 *
154 * Args:
155 * tsc: traceset
156 */
157 void sync_traceset(LttvTracesetContext* const tsc)
158 {
159 SyncState* syncState;
160 struct timeval startTime, endTime;
161 struct rusage startUsage, endUsage;
162 int retval;
163
164 if (optionSync == FALSE)
165 {
166 g_debug("Not synchronizing traceset because option is disabled");
167 return;
168 }
169
170 if (optionSyncStats)
171 {
172 gettimeofday(&startTime, 0);
173 getrusage(RUSAGE_SELF, &startUsage);
174 }
175
176 // Initialize data structures
177 syncState= malloc(sizeof(SyncState));
178 syncState->tsc= tsc;
179 syncState->traceNb= lttv_traceset_number(tsc->ts);
180
181 if (optionSyncStats)
182 {
183 syncState->stats= calloc(1, sizeof(Stats));
184 }
185
186 if (optionSyncData)
187 {
188 syncState->dataFd= fopen(optionSyncData, "w");
189 if (syncState->dataFd == NULL)
190 {
191 perror(0);
192 goto out_free;
193 }
194
195 fprintf(syncState->dataFd, "%10s %10s %21s %21s %21s\n", "ni", "nj",
196 "timoy", "dji", "eji");
197 }
198
199 // Process traceset
200 registerHooks(syncState);
201
202 lttv_process_traceset_seek_time(tsc, ltt_time_zero);
203 lttv_process_traceset_middle(tsc, ltt_time_infinite, G_MAXULONG, NULL);
204 lttv_process_traceset_seek_time(tsc, ltt_time_zero);
205
206 unregisterHooks(syncState);
207
208 // Finalize the least-squares analysis
209 finalizeLSA(syncState);
210
211 // Find a reference node and structure nodes in a graph
212 doGraphProcessing(syncState);
213
214 // Calculate the resulting offset and drift between each trace and its
215 // reference and write those values to the LttTrace structures
216 calculateFactors(syncState);
217
218 if (optionSyncData)
219 {
220 retval= fclose(syncState->dataFd);
221 if (retval != 0)
222 {
223 perror(0);
224 }
225 }
226
227 out_free:
228 if (optionSyncStats)
229 {
230 printf("Stats:\n");
231 // Received frames
232 printf("\ttotal received packets: %d\n", syncState->stats->totRecv);
233 // Received frames that are ip
234 printf("\ttotal received IP packets: %d\n",
235 syncState->stats->totRecvIp);
236 // Processed packets that are tcp
237 printf("\ttotal input events: %d\n", syncState->stats->totInE);
238 // Sent packets that are tcp
239 printf("\ttotal output events: %d\n", syncState->stats->totOutE);
240 // Input and output events were matched together
241 printf("\ttotal packets identified: %d\n",
242 syncState->stats->totPacket);
243 printf("\ttotal packets identified needing an acknowledge: %d\n",
244 syncState->stats->totPacketNeedAck);
245 // Four events are matched
246 printf("\ttotal packets fully acknowledged: %d\n",
247 syncState->stats->totExchangeEffective);
248 // Many packets were acknowledged at once
249 printf("\ttotal packets cummulatively acknowledged (excluding the "
250 "first in each series): %d\n",
251 syncState->stats->totPacketCummAcked);
252 // Offset calculations that could be done, some effective exchanges are
253 // not used when there is cummulative acknowledge
254 printf("\ttotal exchanges identified: %d\n",
255 syncState->stats->totExchangeReal);
256
257 free(syncState->stats);
258 }
259 free(syncState);
260
261 if (optionSyncStats)
262 {
263 gettimeofday(&endTime, 0);
264 retval= getrusage(RUSAGE_SELF, &endUsage);
265
266 timeDiff(&endTime, &startTime);
267 timeDiff(&endUsage.ru_utime, &startUsage.ru_utime);
268 timeDiff(&endUsage.ru_stime, &startUsage.ru_stime);
269
270 printf("Synchronization time:\n");
271 printf("\treal time: %ld.%06ld\n", endTime.tv_sec, endTime.tv_usec);
272 printf("\tuser time: %ld.%06ld\n", endUsage.ru_utime.tv_sec, endUsage.ru_utime.tv_usec);
273 printf("\tsystem time: %ld.%06ld\n", endUsage.ru_stime.tv_sec, endUsage.ru_stime.tv_usec);
274 }
275 }
276
277
278 /*
279 * Allocate and initialize data structures for synchronizing a traceset.
280 * Register event hooks.
281 *
282 * Args:
283 * syncState: container for synchronization data.
284 * This function allocates theses members:
285 * traceNumTable
286 * hookListList
287 * pendingRecv
288 * unMatchedInE
289 * unMatchedOutE
290 * unAcked
291 * fitArray
292 */
293 void registerHooks(SyncState* const syncState)
294 {
295 unsigned int i, j, k;
296
297 // Allocate lists
298 syncState->pendingRecv= g_hash_table_new_full(NULL, NULL, NULL,
299 &netEventListDestroy);
300 syncState->unMatchedInE= g_hash_table_new_full(&netEventPacketHash,
301 &netEventPacketEqual, NULL, &ghtDestroyNetEvent);
302 syncState->unMatchedOutE= g_hash_table_new_full(&netEventPacketHash,
303 &netEventPacketEqual, NULL, &ghtDestroyNetEvent);
304 syncState->unAcked= g_hash_table_new_full(&connectionHash,
305 &connectionEqual, &connectionDestroy, &packetListDestroy);
306
307 syncState->fitArray= malloc(syncState->traceNb * sizeof(Fit*));
308 for (i= 0; i < syncState->traceNb; i++)
309 {
310 syncState->fitArray[i]= calloc(syncState->traceNb, sizeof(Fit));
311 }
312
313 syncState->traceNumTable= g_hash_table_new(&g_direct_hash,
314 &g_direct_equal);
315
316 syncState->hookListList= g_array_sized_new(FALSE, FALSE, sizeof(GArray*),
317 syncState->traceNb);
318
319 // Add event hooks and initialize traceNumTable
320 // note: possibilité de remettre le code avec lttv_trace_find_marker_ids (voir r328)
321 for(i= 0; i < syncState->traceNb; i++)
322 {
323 guint old_len;
324 LttvTraceContext* tc;
325 GArray* hookList;
326 const int hookNb= 5;
327 int retval;
328
329 hookList= g_array_sized_new(FALSE, FALSE, sizeof(LttvTraceHook), hookNb);
330 g_array_append_val(syncState->hookListList, hookList);
331
332 tc= syncState->tsc->traces[i];
333
334 g_hash_table_insert(syncState->traceNumTable, tc->t, (gpointer) i);
335
336 // Find the hooks
337 old_len= hookList->len;
338 retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NET,
339 LTT_EVENT_DEV_HARD_START_XMIT_TCP,
340 FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_SADDR,
341 LTT_FIELD_DADDR, LTT_FIELD_TOT_LEN,
342 LTT_FIELD_IHL, LTT_FIELD_SOURCE,
343 LTT_FIELD_DEST, LTT_FIELD_SEQ,
344 LTT_FIELD_ACK_SEQ, LTT_FIELD_DOFF,
345 LTT_FIELD_ACK, LTT_FIELD_RST, LTT_FIELD_SYN,
346 LTT_FIELD_FIN), process_event_by_id,
347 syncState, &hookList);
348 if (retval != 0)
349 {
350 g_warning("Trace %d contains no %s.%s marker\n", i,
351 g_quark_to_string(LTT_CHANNEL_NET),
352 g_quark_to_string(LTT_EVENT_DEV_HARD_START_XMIT_TCP));
353 }
354 else
355 {
356 g_assert(hookList->len - old_len == 1);
357 }
358
359 old_len= hookList->len;
360 retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NET,
361 LTT_EVENT_DEV_RECEIVE, FIELD_ARRAY(LTT_FIELD_SKB,
362 LTT_FIELD_PROTOCOL), process_event_by_id, syncState, &hookList);
363 if (retval != 0)
364 {
365 g_warning("Trace %d contains no %s.%s marker\n", i,
366 g_quark_to_string(LTT_CHANNEL_NET),
367 g_quark_to_string(LTT_EVENT_DEV_RECEIVE));
368 }
369 else
370 {
371 g_assert(hookList->len - old_len == 1);
372 }
373
374 old_len= hookList->len;
375 retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NET,
376 LTT_EVENT_PKFREE_SKB, FIELD_ARRAY(LTT_FIELD_SKB),
377 process_event_by_id, syncState, &hookList);
378 if (retval != 0)
379 {
380 g_warning("Trace %d contains no %s.%s marker\n", i,
381 g_quark_to_string(LTT_CHANNEL_NET),
382 g_quark_to_string(LTT_EVENT_PKFREE_SKB));
383 }
384 else
385 {
386 g_assert(hookList->len - old_len == 1);
387 }
388
389 old_len= hookList->len;
390 retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NET, LTT_EVENT_TCPV4_RCV,
391 FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_SADDR, LTT_FIELD_DADDR,
392 LTT_FIELD_TOT_LEN, LTT_FIELD_IHL, LTT_FIELD_SOURCE,
393 LTT_FIELD_DEST, LTT_FIELD_SEQ, LTT_FIELD_ACK_SEQ,
394 LTT_FIELD_DOFF, LTT_FIELD_ACK, LTT_FIELD_RST, LTT_FIELD_SYN,
395 LTT_FIELD_FIN), process_event_by_id, syncState, &hookList);
396 if (retval != 0)
397 {
398 g_warning("Trace %d contains no %s.%s marker\n", i,
399 g_quark_to_string(LTT_CHANNEL_NET),
400 g_quark_to_string(LTT_EVENT_TCPV4_RCV));
401 }
402 else
403 {
404 g_assert(hookList->len - old_len == 1);
405 }
406
407 old_len= hookList->len;
408 retval= lttv_trace_find_hook(tc->t, LTT_CHANNEL_NETIF_STATE,
409 LTT_EVENT_NETWORK_IPV4_INTERFACE, FIELD_ARRAY(LTT_FIELD_NAME,
410 LTT_FIELD_ADDRESS, LTT_FIELD_UP), process_event_by_id, syncState,
411 &hookList);
412 if (retval != 0)
413 {
414 g_warning("Trace %d contains no %s.%s marker\n", i,
415 g_quark_to_string(LTT_CHANNEL_NETIF_STATE),
416 g_quark_to_string(LTT_EVENT_NETWORK_IPV4_INTERFACE));
417 }
418 else
419 {
420 g_assert(hookList->len - old_len == 1);
421 }
422
423 // Add the hooks to each tracefile's event_by_id hook list
424 for(j= 0; j < tc->tracefiles->len; j++)
425 {
426 LttvTracefileContext* tfc;
427
428 tfc= g_array_index(tc->tracefiles, LttvTracefileContext*, j);
429
430 for(k= 0; k < hookList->len; k++)
431 {
432 LttvTraceHook* trace_hook;
433
434 trace_hook= &g_array_index(hookList, LttvTraceHook, k);
435 if (trace_hook->hook_data != syncState)
436 {
437 g_assert_not_reached();
438 }
439 if (trace_hook->mdata == tfc->tf->mdata)
440 {
441 lttv_hooks_add(lttv_hooks_by_id_find(tfc->event_by_id,
442 trace_hook->id),
443 trace_hook->h, trace_hook,
444 LTTV_PRIO_DEFAULT);
445 }
446 }
447 }
448 }
449 }
450
451
452 /*
453 * Unregister event hooks. Deallocate some data structures that are not needed
454 * anymore after running the hooks.
455 * Args:
456 * syncState: container for synchronization data.
457 * This function deallocates theses members:
458 * hookListList
459 * pendingRecv
460 * unMatchedInE
461 * unMatchedOutE
462 * unAcked
463 */
464 void unregisterHooks(SyncState* const syncState)
465 {
466 unsigned int i, j, k;
467
468 // Remove event hooks
469 for(i= 0; i < syncState->traceNb; i++)
470 {
471 LttvTraceContext* tc;
472 GArray* hookList;
473
474 tc= syncState->tsc->traces[i];
475 hookList= g_array_index(syncState->hookListList, GArray*, i);
476
477 // Remove the hooks from each tracefile's event_by_id hook list
478 for(j= 0; j < tc->tracefiles->len; j++)
479 {
480 LttvTracefileContext* tfc;
481
482 tfc= g_array_index(tc->tracefiles, LttvTracefileContext*, j);
483
484 for(k= 0; k < hookList->len; k++)
485 {
486 LttvTraceHook* trace_hook;
487
488 trace_hook= &g_array_index(hookList, LttvTraceHook, k);
489 if (trace_hook->mdata == tfc->tf->mdata)
490 {
491 lttv_hooks_remove_data(lttv_hooks_by_id_find(tfc->event_by_id,
492 trace_hook->id), trace_hook->h, trace_hook);
493 }
494 }
495 }
496
497 g_array_free(hookList, TRUE);
498 }
499
500 g_array_free(syncState->hookListList, TRUE);
501
502 // Free lists
503 g_debug("Cleaning up pendingRecv list\n");
504 g_hash_table_destroy(syncState->pendingRecv);
505 g_debug("Cleaning up unMatchedInE list\n");
506 g_hash_table_destroy(syncState->unMatchedInE);
507 g_debug("Cleaning up unMatchedOutE list\n");
508 g_hash_table_destroy(syncState->unMatchedOutE);
509 g_debug("Cleaning up unAcked list\n");
510 g_hash_table_destroy(syncState->unAcked);
511 }
512
513
514 /*
515 * Finalize the least-squares analysis. The intermediate values in the fit
516 * array are used to calculate the drift and the offset between each pair of
517 * nodes based on their exchanges.
518 *
519 * Args:
520 * syncState: container for synchronization data.
521 */
522 void finalizeLSA(SyncState* const syncState)
523 {
524 unsigned int i, j;
525
526 if (optionSyncStats)
527 {
528 printf("Individual synchronization factors:\n");
529 }
530
531 for (i= 0; i < syncState->traceNb; i++)
532 {
533 for (j= 0; j < syncState->traceNb; j++)
534 {
535 if (i != j)
536 {
537 Fit* fit;
538 double delta;
539
540 fit= &syncState->fitArray[i][j];
541
542 delta= fit->n * fit->st2 - pow(fit->st, 2);
543 fit->x= (fit->n * fit->std - fit->st * fit->sd) / delta;
544 fit->d0= (fit->st2 * fit->sd - fit->st * fit->std) / delta;
545 fit->e= sqrt((fit->sd2 - (fit->n * pow(fit->std, 2) +
546 pow(fit->sd, 2) * fit->st2 - 2 * fit->st * fit->sd
547 * fit->std) / delta) / (fit->n - 2));
548
549 g_debug("[i= %u j= %u]\n", i, j);
550 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g\n",
551 fit->n, fit->st, fit->st2, fit->sd, fit->sd2, fit->std);
552 g_debug("xij= %g d0ij= %g e= %g\n", fit->x, fit->d0, fit->e);
553 g_debug("(xji= %g d0ji= %g)\n", -fit->x / (1 + fit->x),
554 -fit->d0 / (1 + fit->x));
555 }
556 }
557 }
558
559 if (optionSyncStats)
560 {
561 for (i= 0; i < syncState->traceNb; i++)
562 {
563 for (j= 0; j < syncState->traceNb; j++)
564 {
565 if (i < j)
566 {
567 Fit* fit;
568
569 fit= &syncState->fitArray[i][j];
570 printf("\tbetween trace i= %u and j= %u, xij= %g d0ij= %g "
571 "e= %g\n", i, j, fit->x, fit->d0, fit->e);
572
573 fit= &syncState->fitArray[j][i];
574 printf("\tbetween trace i= %u and j= %u, xij= %g d0ij= %g "
575 "e= %g\n", j, i, fit->x, fit->d0, fit->e);
576 }
577 }
578 }
579 }
580 }
581
582
583 /*
584 * Structure nodes in graphs of nodes that had exchanges. Each graph has a
585 * reference node, the one that can reach the others with the smallest
586 * cummulative error.
587 *
588 * Args:
589 * syncState: container for synchronization data.
590 * This function allocates these members:
591 * graphList
592 */
593 void doGraphProcessing(SyncState* const syncState)
594 {
595 unsigned int i, j;
596 double* distances;
597 unsigned int* previousVertex;
598
599 distances= malloc(syncState->traceNb * sizeof(double));
600 previousVertex= malloc(syncState->traceNb * sizeof(unsigned int));
601 syncState->graphList= g_queue_new();
602
603 for (i= 0; i < syncState->traceNb; i++)
604 {
605 double errorSum;
606 GList* result;
607
608 // Perform shortest path search
609 g_debug("shortest path trace %d\ndistances: ", i);
610 shortestPath(syncState->fitArray, i, syncState->traceNb, distances,
611 previousVertex);
612
613 for (j= 0; j < syncState->traceNb; j++)
614 {
615 g_debug("%g, ", distances[j]);
616 }
617 g_debug("\npreviousVertex: ");
618 for (j= 0; j < syncState->traceNb; j++)
619 {
620 g_debug("%u, ", previousVertex[j]);
621 }
622 g_debug("\n");
623
624 // Group in graphs nodes that have exchanges
625 errorSum= sumDistances(distances, syncState->traceNb);
626 result= g_queue_find_custom(syncState->graphList, &i,
627 &graphTraceCompare);
628 if (result != NULL)
629 {
630 Graph* graph;
631
632 g_debug("found graph\n");
633 graph= (Graph*) result->data;
634 if (errorSum < graph->errorSum)
635 {
636 g_debug("adding to graph\n");
637 graph->errorSum= errorSum;
638 free(graph->previousVertex);
639 graph->previousVertex= previousVertex;
640 graph->reference= i;
641 previousVertex= malloc(syncState->traceNb * sizeof(unsigned
642 int));
643 }
644 }
645 else
646 {
647 Graph* newGraph;
648
649 g_debug("creating new graph\n");
650 newGraph= malloc(sizeof(Graph));
651 newGraph->errorSum= errorSum;
652 newGraph->previousVertex= previousVertex;
653 newGraph->reference= i;
654 previousVertex= malloc(syncState->traceNb * sizeof(unsigned int));
655
656 g_queue_push_tail(syncState->graphList, newGraph);
657 }
658 }
659
660 free(previousVertex);
661 free(distances);
662 }
663
664
665 /*
666 * Calculate the resulting offset and drift between each trace and its
667 * reference and write those values to the LttTrace structures. Also free
668 * structures that are not needed anymore.
669 *
670 * Args:
671 * syncState: container for synchronization data.
672 * This function deallocates:
673 * traceNumTable
674 * fitArray
675 * graphList
676 */
677 void calculateFactors(SyncState* const syncState)
678 {
679 unsigned int i, j;
680 double minOffset;
681
682 // Calculate the resulting offset and drift between each trace and its
683 // reference
684 g_info("Factors:\n");
685 if (optionSyncStats)
686 {
687 printf("Resulting synchronization factors:\n");
688 }
689
690 minOffset= 0;
691 for (i= 0; i < syncState->traceNb; i++)
692 {
693 GList* result;
694
695 result= g_queue_find_custom(syncState->graphList, &i,
696 &graphTraceCompare);
697 if (result != NULL)
698 {
699 Graph* graph;
700 double drift, offset, stDev;
701 LttTrace* t;
702
703 t= syncState->tsc->traces[i]->t;
704 graph= (Graph*) result->data;
705
706 g_info("trace %u (%p) graph: reference %u\n", i, t, graph->reference);
707
708 for (j= 0; j < syncState->traceNb; j++)
709 {
710 g_info("%u, ", graph->previousVertex[j]);
711 }
712 g_info("\n");
713
714 factors(syncState->fitArray, graph->previousVertex, i, &drift,
715 &offset, &stDev);
716 t->drift= drift;
717 t->offset= offset;
718 t->start_time_from_tsc =
719 ltt_time_from_uint64(tsc_to_uint64(t->freq_scale,
720 t->start_freq, drift * t->start_tsc + offset));
721
722 if (optionSyncStats)
723 {
724 if (i == graph->reference)
725 {
726 printf("\ttrace %u reference %u previous vertex - "
727 "stdev= %g\n", i,
728 graph->reference, stDev);
729 }
730 else
731 {
732 printf("\ttrace %u reference %u previous vertex %u "
733 "stdev= %g\n", i,
734 graph->reference,
735 graph->previousVertex[i],
736 stDev);
737 }
738 }
739
740 if (offset < minOffset)
741 {
742 minOffset= offset;
743 }
744 }
745 else
746 {
747 fprintf(stderr, "trace: %d\n", i);
748 g_assert_not_reached();
749 }
750 }
751
752 // Adjust all offsets so the lowest one is 0 (no negative offsets)
753 for (i= 0; i < syncState->traceNb; i++)
754 {
755 LttTrace* t;
756
757 t= syncState->tsc->traces[i]->t;
758 t->offset-= minOffset;
759 t->start_time_from_tsc =
760 ltt_time_from_uint64(tsc_to_uint64(t->freq_scale,
761 t->start_freq, t->drift * t->start_tsc
762 + t->offset));
763
764 g_info("trace %u drift: %f offset: %g start_time: %ld.%09ld\n",
765 i, t->drift, t->offset, t->start_time_from_tsc.tv_sec,
766 t->start_time_from_tsc.tv_nsec);
767
768 if (optionSyncStats)
769 {
770 printf("\ttrace %u drift= %g offset= %g (%f)\n", i,
771 t->drift, t->offset,
772 tsc_to_uint64(t->freq_scale, t->start_freq,
773 t->offset) / 1e9);
774 }
775 }
776
777 lttv_traceset_context_compute_time_span(syncState->tsc,
778 &syncState->tsc->time_span);
779
780 g_debug("traceset start %ld.%09ld end %ld.%09ld\n",
781 syncState->tsc->time_span.start_time.tv_sec,
782 syncState->tsc->time_span.start_time.tv_nsec,
783 syncState->tsc->time_span.end_time.tv_sec,
784 syncState->tsc->time_span.end_time.tv_nsec);
785
786 g_queue_foreach(syncState->graphList, &graphRemove, NULL);
787 g_queue_free(syncState->graphList);
788
789 for (i= 0; i < syncState->traceNb; i++)
790 {
791 free(syncState->fitArray[i]);
792 }
793 free(syncState->fitArray);
794
795 g_hash_table_destroy(syncState->traceNumTable);
796 }
797
798
799 /*
800 * Lttv hook function that will be called for network events
801 *
802 * Args:
803 * hook_data: LttvTraceHook* for the type of event that generated the call
804 * call_data: LttvTracefileContext* at the moment of the event
805 *
806 * Returns:
807 * FALSE Always returns FALSE, meaning to keep processing hooks for
808 * this event
809 */
810 static gboolean process_event_by_id(void* hook_data, void* call_data)
811 {
812 LttvTraceHook* trace_hook;
813 LttvTracefileContext* tfc;
814 LttEvent* event;
815 LttTime time;
816 LttCycleCount tsc;
817 LttTrace* trace;
818 struct marker_info* info;
819 SyncState* syncState;
820
821 trace_hook= (LttvTraceHook*) hook_data;
822 tfc= (LttvTracefileContext*) call_data;
823 syncState= (SyncState*) trace_hook->hook_data;
824 event= ltt_tracefile_get_event(tfc->tf);
825 time= ltt_event_time(event);
826 tsc= ltt_event_cycle_count(event);
827 trace= tfc->t_context->t;
828 info= marker_get_info_from_id(tfc->tf->mdata, event->event_id);
829
830 g_debug("XXXX process event: time: %ld.%09ld trace: %p name: %s ",
831 (long) time.tv_sec, time.tv_nsec, trace,
832 g_quark_to_string(info->name));
833
834 if (info->name == LTT_EVENT_DEV_HARD_START_XMIT_TCP)
835 {
836 NetEvent* outE;
837
838 if (optionSyncStats)
839 {
840 syncState->stats->totOutE++;
841 }
842
843 outE= malloc(sizeof(NetEvent));
844
845 outE->packet= NULL;
846 outE->trace= trace;
847 outE->tsc= tsc;
848
849 matchEvents(outE, syncState->unMatchedOutE, syncState->unMatchedInE,
850 event, trace_hook, offsetof(Packet, outE));
851
852 g_debug("Output event done\n");
853 }
854 else if (info->name == LTT_EVENT_DEV_RECEIVE)
855 {
856 NetEvent* inE;
857 guint64 protocol;
858
859 if (optionSyncStats)
860 {
861 syncState->stats->totRecv++;
862 }
863
864 protocol= ltt_event_get_long_unsigned(event,
865 lttv_trace_get_hook_field(trace_hook, 1));
866
867 if (protocol == ETH_P_IP)
868 {
869 GQueue* list;
870
871 if (optionSyncStats)
872 {
873 syncState->stats->totRecvIp++;
874 }
875
876 inE= malloc(sizeof(NetEvent));
877
878 inE->packet= NULL;
879 inE->trace= trace;
880 inE->tsc= tsc;
881 inE->skb= (void*) (unsigned long)
882 ltt_event_get_long_unsigned(event,
883 lttv_trace_get_hook_field(trace_hook, 0));
884
885 list= g_hash_table_lookup(syncState->pendingRecv, trace);
886 if (unlikely(list == NULL))
887 {
888 g_hash_table_insert(syncState->pendingRecv, trace, list=
889 g_queue_new());
890 }
891 g_queue_push_head(list, inE);
892
893 g_debug("Adding inE to pendingRecv\n");
894 }
895 else
896 {
897 g_debug("\n");
898 }
899 }
900 else if (info->name == LTT_EVENT_TCPV4_RCV)
901 {
902 GQueue* prList;
903
904 // Search pendingRecv for an event with the same skb
905 prList= g_hash_table_lookup(syncState->pendingRecv, trace);
906 if (unlikely(prList == NULL))
907 {
908 g_debug("No pending receive event list for this trace\n");
909 }
910 else
911 {
912 NetEvent tempInE;
913 GList* result;
914
915 tempInE.skb= (void*) (unsigned long)
916 ltt_event_get_long_unsigned(event,
917 lttv_trace_get_hook_field(trace_hook, 0));
918 result= g_queue_find_custom(prList, &tempInE, &netEventSkbCompare);
919
920 if (result == NULL)
921 {
922 g_debug("No matching pending receive event found\n");
923 }
924 else
925 {
926 NetEvent* inE;
927
928 if (optionSyncStats)
929 {
930 syncState->stats->totInE++;
931 }
932
933 // If it's there, remove it and proceed with a receive event
934 inE= (NetEvent*) result->data;
935 g_queue_delete_link(prList, result);
936
937 matchEvents(inE, syncState->unMatchedInE,
938 syncState->unMatchedOutE, event, trace_hook,
939 offsetof(Packet, inE));
940
941 g_debug("Input event done\n");
942 }
943 }
944 }
945 else if (info->name == LTT_EVENT_PKFREE_SKB)
946 {
947 GQueue* list;
948
949 list= g_hash_table_lookup(syncState->pendingRecv, trace);
950 if (unlikely(list == NULL))
951 {
952 g_debug("No pending receive event list for this trace\n");
953 }
954 else
955 {
956 NetEvent tempInE;
957 GList* result;
958
959 tempInE.skb= (void*) (unsigned long)
960 ltt_event_get_long_unsigned(event,
961 lttv_trace_get_hook_field(trace_hook, 0));
962 result= g_queue_find_custom(list, &tempInE, &netEventSkbCompare);
963
964 if (result == NULL)
965 {
966 g_debug("No matching pending receive event found, \"shaddow"
967 "skb\"\n");
968 }
969 else
970 {
971 NetEvent* inE;
972
973 inE= (NetEvent*) result->data;
974 g_queue_delete_link(list, result);
975 destroyNetEvent(inE);
976
977 g_debug("Non-TCP skb\n");
978 }
979 }
980 }
981 else if (info->name == LTT_EVENT_NETWORK_IPV4_INTERFACE)
982 {
983 char* name;
984 guint64 address;
985 gint64 up;
986 char addressString[17];
987
988 name= ltt_event_get_string(event, lttv_trace_get_hook_field(trace_hook,
989 0));
990 address= ltt_event_get_long_unsigned(event,
991 lttv_trace_get_hook_field(trace_hook, 1));
992 up= ltt_event_get_long_int(event, lttv_trace_get_hook_field(trace_hook,
993 2));
994
995 convertIP(addressString, address);
996
997 g_debug("name \"%s\" address %s up %lld\n", name, addressString, up);
998 }
999 else
1000 {
1001 g_debug("<default>\n");
1002 }
1003
1004 return FALSE;
1005 }
1006
1007
1008 /*
1009 * Implementation of a packet matching algorithm for TCP
1010 *
1011 * Args:
1012 * netEvent new event to match
1013 * unMatchedList list of unmatched events of the same type (send or receive)
1014 * as netEvent
1015 * unMatchedOppositeList list of unmatched events of the opposite type of
1016 * netEvent
1017 * event event corresponding to netEvent
1018 * trace_hook trace_hook corresponding to netEvent
1019 * fieldOffset offset of the NetEvent field in the Packet struct for the
1020 * field of the type of netEvent
1021 */
1022 static void matchEvents(NetEvent* const netEvent, GHashTable* const
1023 unMatchedList, GHashTable* const unMatchedOppositeList, LttEvent* const
1024 event, LttvTraceHook* const trace_hook, const size_t fieldOffset)
1025 {
1026 Packet* packet;
1027 GQueue* uaList;
1028 GList* result;
1029 SyncState* syncState;
1030 NetEvent* companionEvent;
1031
1032 syncState= (SyncState*) trace_hook->hook_data;
1033
1034 // Search unmatched list of opposite type for a matching event
1035 packet= malloc(sizeof(Packet));
1036 packet->connKey.saddr= ltt_event_get_long_unsigned(event,
1037 lttv_trace_get_hook_field(trace_hook, 1));
1038 packet->connKey.daddr= ltt_event_get_long_unsigned(event,
1039 lttv_trace_get_hook_field(trace_hook, 2));
1040 packet->tot_len= ltt_event_get_long_unsigned(event,
1041 lttv_trace_get_hook_field(trace_hook, 3));
1042 packet->ihl= ltt_event_get_long_unsigned(event,
1043 lttv_trace_get_hook_field(trace_hook, 4));
1044 packet->connKey.source= ltt_event_get_long_unsigned(event,
1045 lttv_trace_get_hook_field(trace_hook, 5));
1046 packet->connKey.dest= ltt_event_get_long_unsigned(event,
1047 lttv_trace_get_hook_field(trace_hook, 6));
1048 packet->seq= ltt_event_get_long_unsigned(event,
1049 lttv_trace_get_hook_field(trace_hook, 7));
1050 packet->ack_seq= ltt_event_get_long_unsigned(event,
1051 lttv_trace_get_hook_field(trace_hook, 8));
1052 packet->doff= ltt_event_get_long_unsigned(event,
1053 lttv_trace_get_hook_field(trace_hook, 9));
1054 packet->ack= ltt_event_get_long_unsigned(event,
1055 lttv_trace_get_hook_field(trace_hook, 10));
1056 packet->rst= ltt_event_get_long_unsigned(event,
1057 lttv_trace_get_hook_field(trace_hook, 11));
1058 packet->syn= ltt_event_get_long_unsigned(event,
1059 lttv_trace_get_hook_field(trace_hook, 12));
1060 packet->fin= ltt_event_get_long_unsigned(event,
1061 lttv_trace_get_hook_field(trace_hook, 13));
1062 packet->inE= packet->outE= NULL;
1063 packet->acks= NULL;
1064
1065 companionEvent= g_hash_table_lookup(unMatchedOppositeList, packet);
1066 if (companionEvent != NULL)
1067 {
1068 if (optionSyncStats)
1069 {
1070 syncState->stats->totPacket++;
1071 }
1072
1073 g_debug("Found matching companion event, ");
1074 // If it's there, remove it and update the structures
1075 g_hash_table_steal(unMatchedOppositeList, packet);
1076 free(packet);
1077 packet= companionEvent->packet;
1078 *((NetEvent**) ((void*) packet + fieldOffset))= netEvent;
1079
1080 // If this packet acknowleges some data ...
1081 if (isAck(packet))
1082 {
1083 uaList= g_hash_table_lookup(syncState->unAcked, &packet->connKey);
1084 if (uaList != NULL)
1085 {
1086 Packet* ackedPacket;
1087
1088 result= g_queue_find_custom(uaList, packet, &packetAckCompare);
1089
1090 while (result != NULL)
1091 {
1092 // Remove the acknowledged packet from the unAcked list
1093 // and keep this packet for later offset calculations
1094 g_debug("Found matching unAcked packet, ");
1095
1096 ackedPacket= (Packet*) result->data;
1097 g_queue_delete_link(uaList, result);
1098
1099 // If the acked packet doesn't have both of its events,
1100 // remove the orphaned event from the corresponding
1101 // unmatched list and destroy the acked packet (an event
1102 // was not in the trace)
1103 if (ackedPacket->inE == NULL)
1104 {
1105 g_hash_table_steal(syncState->unMatchedOutE, packet);
1106 destroyPacket(ackedPacket);
1107 }
1108 else if (ackedPacket->outE == NULL)
1109 {
1110 g_hash_table_steal(syncState->unMatchedInE, packet);
1111 destroyPacket(ackedPacket);
1112 }
1113 else
1114 {
1115 if (optionSyncStats)
1116 {
1117 syncState->stats->totExchangeEffective++;
1118 }
1119
1120 if (packet->acks == NULL)
1121 {
1122 packet->acks= g_queue_new();
1123 }
1124 else if (optionSyncStats)
1125 {
1126 syncState->stats->totPacketCummAcked++;
1127 }
1128
1129 g_queue_push_tail(packet->acks, ackedPacket);
1130 }
1131
1132 result= g_queue_find_custom(uaList, packet,
1133 &packetAckCompare);
1134 }
1135
1136 // It might be possible to do an offset calculation
1137 if (packet->acks != NULL)
1138 {
1139 if (optionSyncStats)
1140 {
1141 syncState->stats->totExchangeReal++;
1142 }
1143
1144 g_debug("Synchronization calculation, ");
1145 g_debug("%d acked packets - using last one, ",
1146 g_queue_get_length(packet->acks));
1147
1148 ackedPacket= g_queue_peek_tail(packet->acks);
1149 if (ackedPacket->outE->trace != packet->inE->trace ||
1150 ackedPacket->inE->trace != packet->outE->trace)
1151 {
1152 g_debug("disorganized exchange - discarding, ");
1153 }
1154 else if (ackedPacket->outE->trace ==
1155 ackedPacket->inE->trace)
1156 {
1157 g_debug("packets from the same trace - discarding, ");
1158 }
1159 else
1160 {
1161 double dji, eji;
1162 double timoy;
1163 unsigned int ni, nj;
1164 LttTrace* orig_key;
1165 Fit* fit;
1166
1167 // Calculate the intermediate values for the
1168 // least-squares analysis
1169 dji= ((double) ackedPacket->inE->tsc - (double)
1170 ackedPacket->outE->tsc + (double) packet->outE->tsc
1171 - (double) packet->inE->tsc) / 2;
1172 eji= fabs((double) ackedPacket->inE->tsc - (double)
1173 ackedPacket->outE->tsc - (double) packet->outE->tsc
1174 + (double) packet->inE->tsc) / 2;
1175 timoy= ((double) ackedPacket->outE->tsc + (double)
1176 packet->inE->tsc) / 2;
1177 g_assert(g_hash_table_lookup_extended(syncState->traceNumTable,
1178 ackedPacket->outE->trace, (gpointer*)
1179 &orig_key, (gpointer*) &ni));
1180 g_assert(g_hash_table_lookup_extended(syncState->traceNumTable,
1181 ackedPacket->inE->trace, (gpointer*)
1182 &orig_key, (gpointer*) &nj));
1183 fit= &syncState->fitArray[nj][ni];
1184
1185 fit->n++;
1186 fit->st+= timoy;
1187 fit->st2+= pow(timoy, 2);
1188 fit->sd+= dji;
1189 fit->sd2+= pow(dji, 2);
1190 fit->std+= timoy * dji;
1191
1192 g_debug("intermediate values: dji= %f ti moy= %f "
1193 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
1194 "sd2= %f std= %f, ", dji, timoy, ni, nj, fit->n,
1195 fit->st, fit->st2, fit->sd, fit->sd2, fit->std);
1196
1197 if (optionSyncData)
1198 {
1199 double freq;
1200
1201 freq= syncState->tsc->traces[ni]->t->start_freq *
1202 syncState->tsc->traces[ni]->t->freq_scale;
1203
1204 fprintf(syncState->dataFd, "%10u %10u %21.10f %21.10f %21.10f\n", ni,
1205 nj, timoy / freq, dji / freq, eji / freq);
1206 }
1207 }
1208 }
1209 }
1210 }
1211
1212 if (needsAck(packet))
1213 {
1214 if (optionSyncStats)
1215 {
1216 syncState->stats->totPacketNeedAck++;
1217 }
1218
1219 // If this packet will generate an ack, add it to the unAcked list
1220 g_debug("Adding to unAcked, ");
1221 uaList= g_hash_table_lookup(syncState->unAcked, &packet->connKey);
1222 if (uaList == NULL)
1223 {
1224 ConnectionKey* connKey;
1225
1226 connKey= malloc(sizeof(ConnectionKey));
1227 memcpy(connKey, &packet->connKey, sizeof(ConnectionKey));
1228 g_hash_table_insert(syncState->unAcked, connKey, uaList= g_queue_new());
1229 }
1230 g_queue_push_tail(uaList, packet);
1231 }
1232 else
1233 {
1234 destroyPacket(packet);
1235 }
1236 }
1237 else
1238 {
1239 // If there's no corresponding event, finish creating the data
1240 // structures and add an event to the unmatched list for this type of
1241 // event
1242 netEvent->packet= packet;
1243 *((NetEvent**) ((void*) packet + fieldOffset))= netEvent;
1244
1245 g_debug("Adding to unmatched event list, ");
1246 g_hash_table_insert(unMatchedList, packet, netEvent);
1247 }
1248 }
1249
1250
1251 /*
1252 * Check if a packet is an acknowledge
1253 *
1254 * Returns:
1255 * true if it is,
1256 * false otherwise
1257 */
1258 static bool isAck(const Packet* const packet)
1259 {
1260 if (packet->ack == 1)
1261 {
1262 return true;
1263 }
1264 else
1265 {
1266 return false;
1267 }
1268 }
1269
1270
1271 /*
1272 * Check if a packet is an acknowledge of another packet.
1273 *
1274 * Args:
1275 * ackPacket packet that is the confirmation
1276 * ackedPacket packet that contains the original data, both packets have to
1277 * come from the same connection
1278 */
1279 static bool isAcking(const Packet* const ackPacket, const Packet* const ackedPacket)
1280 {
1281 if (ackedPacket->connKey.saddr == ackPacket->connKey.daddr &&
1282 ackedPacket->connKey.daddr == ackPacket->connKey.saddr &&
1283 ackedPacket->connKey.source == ackPacket->connKey.dest &&
1284 ackedPacket->connKey.dest == ackPacket->connKey.source &&
1285 ackPacket->ack_seq > ackedPacket->seq)
1286 {
1287 return true;
1288 }
1289 else
1290 {
1291 return false;
1292 }
1293 }
1294
1295
1296 /*
1297 * Check if a packet will increment the sequence number, thus needing an
1298 * acknowledge
1299 *
1300 * Returns:
1301 * true if the packet will need an acknowledge
1302 * false otherwise
1303 */
1304 static bool needsAck(const Packet* const packet)
1305 {
1306 if (packet->syn || packet->fin || packet->tot_len - packet->ihl * 4 -
1307 packet->doff * 4 > 0)
1308 {
1309 return true;
1310 }
1311 else
1312 {
1313 return false;
1314 }
1315 }
1316
1317
1318 /*
1319 * Compare two ConnectionKey structures
1320 *
1321 * Returns:
1322 * true if each field of the structure is equal
1323 * false otherwise
1324 */
1325 static bool connectionKeyEqual(const ConnectionKey* const a, const ConnectionKey* const b)
1326 {
1327 if (a->saddr == b->saddr && a->daddr == b->daddr && a->source ==
1328 b->source && a->dest == b->dest)
1329 {
1330 return true;
1331 }
1332 else
1333 {
1334 return false;
1335 }
1336 }
1337
1338
1339 /*
1340 * A GDestroyNotify function for g_hash_table_new_full()
1341 *
1342 * Args:
1343 * data: GQueue* list[NetEvent]
1344 */
1345 static void netEventListDestroy(gpointer data)
1346 {
1347 GQueue* list;
1348
1349 list= (GQueue*) data;
1350
1351 g_debug("XXXX netEventListDestroy\n");
1352 g_queue_foreach(list, &netEventRemove, NULL);
1353 g_queue_free(list);
1354 }
1355
1356
1357 /*
1358 * A GFunc for g_queue_foreach()
1359 *
1360 * Args:
1361 * data: NetEvent* event
1362 * user_data: NULL
1363 */
1364 static void netEventRemove(gpointer data, gpointer user_data)
1365 {
1366 destroyNetEvent((NetEvent*) data);
1367 }
1368
1369
1370 /*
1371 * A GHashFunc for g_hash_table_new()
1372 *
1373 * This function is for indexing netEvents in unMatched lists. All fields of
1374 * the corresponding packet must match for two keys to be equal.
1375 *
1376 * Args:
1377 * key Packet*
1378 */
1379 static guint netEventPacketHash(gconstpointer key)
1380 {
1381 const Packet* p;
1382 uint32_t a, b, c;
1383
1384 p= key;
1385
1386 a= p->connKey.source + (p->connKey.dest << 16);
1387 b= p->connKey.saddr;
1388 c= p->connKey.daddr;
1389 mix(a, b, c);
1390
1391 a+= p->tot_len;
1392 b+= p->ihl;
1393 c+= p->seq;
1394 mix(a, b, c);
1395
1396 a+= p->ack_seq;
1397 b+= p->doff;
1398 c+= p->ack;
1399 mix(a, b, c);
1400
1401 a+= p->rst;
1402 b+= p->syn;
1403 c+= p->fin;
1404 final(a, b, c);
1405
1406 return c;
1407 }
1408
1409
1410 /*
1411 * A GEqualFunc for g_hash_table_new()
1412 *
1413 * This function is for indexing netEvents in unMatched lists. All fields of
1414 * the corresponding packet must match for two keys to be equal.
1415 *
1416 * Args:
1417 * a, b Packet*
1418 *
1419 * Returns:
1420 * TRUE if both values are equal
1421 */
1422 static gboolean netEventPacketEqual(gconstpointer a, gconstpointer b)
1423 {
1424 const Packet* pA, * pB;
1425
1426 pA= a;
1427 pB= b;
1428
1429 if (connectionKeyEqual(&pA->connKey, &pB->connKey) &&
1430 pA->tot_len == pB->tot_len &&
1431 pA->ihl == pB->ihl &&
1432 pA->seq == pB->seq &&
1433 pA->ack_seq == pB->ack_seq &&
1434 pA->doff == pB->doff &&
1435 pA->ack == pB->ack &&
1436 pA->rst == pB->rst &&
1437 pA->syn == pB->syn &&
1438 pA->fin == pB->fin)
1439 {
1440 return TRUE;
1441 }
1442 else
1443 {
1444 return FALSE;
1445 }
1446 }
1447
1448
1449 /*
1450 * A GDestroyNotify function for g_hash_table_new_full()
1451 *
1452 * Args:
1453 * data: NetEvent*
1454 */
1455 static void ghtDestroyNetEvent(gpointer data)
1456 {
1457 destroyNetEvent((NetEvent*) data);
1458 }
1459
1460
1461 /*
1462 * A GDestroyNotify function for g_hash_table_new_full()
1463 *
1464 * Args:
1465 * data: GQueue* list[Packet]
1466 */
1467 static void packetListDestroy(gpointer data)
1468 {
1469 GQueue* list;
1470
1471 list= (GQueue*) data;
1472
1473 g_debug("XXXX packetListDestroy\n");
1474
1475 g_queue_foreach(list, &packetRemove, NULL);
1476 g_queue_free(list);
1477 }
1478
1479
1480 /*
1481 * A GFunc for g_queue_foreach()
1482 *
1483 * Args:
1484 * data Packet*, packet to destroy
1485 * user_data NULL
1486 */
1487 static void packetRemove(gpointer data, gpointer user_data)
1488 {
1489 Packet* packet;
1490
1491 packet= (Packet*) data;
1492
1493 g_debug("XXXX packetRemove\n");
1494 destroyPacket(packet);
1495 }
1496
1497
1498 /*
1499 * Free the memory used by a Packet and the memory of all its associated
1500 * resources
1501 */
1502 static void destroyPacket(Packet* const packet)
1503 {
1504 g_debug("XXXX destroyPacket ");
1505 printPacket(packet);
1506 g_debug("\n");
1507
1508 if (packet->inE)
1509 {
1510 free(packet->inE);
1511 }
1512
1513 if (packet->outE)
1514 {
1515 free(packet->outE);
1516 }
1517
1518 if (packet->acks)
1519 {
1520 g_queue_foreach(packet->acks, &packetRemove, NULL);
1521 g_queue_free(packet->acks);
1522 }
1523
1524 free(packet);
1525 }
1526
1527
1528 /*
1529 * Free the memory used by a NetEvent and the memory of all its associated
1530 * resources. If the netEvent is part of a packet that also contains the other
1531 * netEvent, that one will be freed also. Beware not to keep references to that
1532 * other one.
1533 */
1534 static void destroyNetEvent(NetEvent* const event)
1535 {
1536 g_debug("XXXX destroyNetEvent\n");
1537 if (event->packet)
1538 {
1539 destroyPacket(event->packet);
1540 }
1541 else
1542 {
1543 free(event);
1544 }
1545 }
1546
1547
1548 /*
1549 * A GFunc for g_queue_foreach()
1550 *
1551 * Args:
1552 * data Graph*, graph to destroy
1553 * user_data NULL
1554 */
1555 static void graphRemove(gpointer data, gpointer user_data)
1556 {
1557 Graph* graph;
1558
1559 graph= (Graph*) data;
1560
1561 free(graph->previousVertex);
1562 free(graph);
1563 }
1564
1565
1566 /*
1567 * A GCompareFunc for g_queue_find_custom()
1568 *
1569 * Args:
1570 * a: NetEvent*
1571 * b: NetEvent*
1572 *
1573 * Returns
1574 * 0 if the two events have the same skb
1575 */
1576 static gint netEventSkbCompare(gconstpointer a, gconstpointer b)
1577 {
1578 if (((NetEvent*) a)->skb == ((NetEvent*) b)->skb)
1579 {
1580 return 0;
1581 }
1582 else
1583 {
1584 return 1;
1585 }
1586 }
1587
1588
1589 /*
1590 * A GCompareFunc to be used with g_queue_find_custom()
1591 *
1592 * Args:
1593 * a NetEvent*
1594 * b NetEvent*
1595 *
1596 * Returns:
1597 * 0 if the two net events correspond to the send and receive events of the
1598 * same packet
1599 */
1600 static gint netEventPacketCompare(gconstpointer a, gconstpointer b)
1601 {
1602 Packet* pA, * pB;
1603
1604 pA= ((NetEvent*) a)->packet;
1605 pB= ((NetEvent*) b)->packet;
1606
1607 if (netEventPacketEqual(a, b))
1608 {
1609 return 0;
1610 }
1611 else
1612 {
1613 return 1;
1614 }
1615 }
1616
1617
1618 /*
1619 * A GCompareFunc for g_queue_find_custom()
1620 *
1621 * Args:
1622 * a Packet* acked packet
1623 * b Packet* ack packet
1624 *
1625 * Returns:
1626 * 0 if b acks a
1627 */
1628 static gint packetAckCompare(gconstpointer a, gconstpointer b)
1629 {
1630 if (isAcking(((Packet*) b), ((Packet*) a)))
1631 {
1632 return 0;
1633 }
1634 else
1635 {
1636 return 1;
1637 }
1638 }
1639
1640
1641 /*
1642 * A GCompareFunc for g_queue_find_custom()
1643 *
1644 * Args:
1645 * a: Graph* graph
1646 * b: unsigned int* traceNum
1647 *
1648 * Returns:
1649 * 0 if graph contains traceNum
1650 */
1651 static gint graphTraceCompare(gconstpointer a, gconstpointer b)
1652 {
1653 Graph* graph;
1654 unsigned int traceNum;
1655
1656 graph= (Graph*) a;
1657 traceNum= *(unsigned int *) b;
1658
1659 if (graph->previousVertex[traceNum] != UINT_MAX)
1660 {
1661 return 0;
1662 }
1663 else if (graph->reference == traceNum)
1664 {
1665 return 0;
1666 }
1667 else
1668 {
1669 return 1;
1670 }
1671 }
1672
1673
1674 /*
1675 * A GHashFunc for g_hash_table_new()
1676 *
1677 * 2.4 kernels used tcp_hashfn(),
1678 *
1679 * I've seen something about an XOR hash:
1680 * http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14:
1681 * unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
1682 * h ^= h >> 16;
1683 * h ^= h >> 8;
1684 * return h;
1685 *
1686 * and in 2.6 kernels inet_ehashfn() handles connection hashing with the help of
1687 * Jenkins hashing, jhash.h
1688 *
1689 * This function uses the XOR method.
1690 *
1691 * Args:
1692 * key ConnectionKey*
1693 */
1694 static guint connectionHash(gconstpointer key)
1695 {
1696 ConnectionKey* connKey;
1697 guint result;
1698
1699 connKey= (ConnectionKey*) key;
1700
1701 result= (connKey->saddr ^ connKey->source) ^ (connKey->daddr ^ connKey->dest);
1702 result^= result >> 16;
1703 result^= result >> 8;
1704
1705 return result;
1706 }
1707
1708
1709 /*
1710 * A GEqualFunc for g_hash_table_new()
1711 *
1712 * Args:
1713 * a, b ConnectionKey*
1714 *
1715 * Returns:
1716 * TRUE if both values are equal
1717 */
1718 static gboolean connectionEqual(gconstpointer a, gconstpointer b)
1719 {
1720 ConnectionKey* ckA, * ckB;
1721
1722 ckA= (ConnectionKey*) a;
1723 ckB= (ConnectionKey*) b;
1724
1725 // Two packets in the same direction
1726 if (ckA->saddr == ckB->saddr && ckA->daddr == ckB->daddr && ckA->source ==
1727 ckB->source && ckA->dest == ckB->dest)
1728 {
1729 return TRUE;
1730 }
1731 // Two packets in opposite directions
1732 else if (ckA->saddr == ckB->daddr && ckA->daddr == ckB->saddr &&
1733 ckA->source == ckB->dest && ckA->dest == ckB->source)
1734 {
1735 return TRUE;
1736 }
1737 else
1738 {
1739 return FALSE;
1740 }
1741 }
1742
1743
1744 /*
1745 * A GDestroyNotify function for g_hash_table_new_full()
1746 *
1747 * Args:
1748 * data: ConnectionKey*
1749 */
1750 static void connectionDestroy(gpointer data)
1751 {
1752 free((ConnectionKey*) data);
1753 }
1754
1755
1756 /*
1757 * Convert an IP address from 32 bit form to dotted quad
1758 *
1759 * Args:
1760 * str: A preallocated string of length >= 17
1761 * addr: Address
1762 */
1763 static void convertIP(char* const str, const uint32_t addr)
1764 {
1765 struct in_addr iaddr;
1766
1767 iaddr.s_addr= htonl(addr);
1768 strcpy(str, inet_ntoa(iaddr));
1769 }
1770
1771
1772 /*
1773 * Print the content of a Packet structure
1774 */
1775 static void printPacket(const Packet* const packet)
1776 {
1777 char saddr[17], daddr[17];
1778
1779 convertIP(saddr, packet->connKey.saddr);
1780 convertIP(daddr, packet->connKey.daddr);
1781 g_debug("%s:%u to %s:%u tot_len: %u ihl: %u seq: %u ack_seq: %u doff: %u "
1782 "ack: %u rst: %u syn: %u fin: %u", saddr, packet->connKey.source,
1783 daddr, packet->connKey.dest, packet->tot_len, packet->ihl, packet->seq,
1784 packet->ack_seq, packet->doff, packet->ack, packet->rst, packet->syn,
1785 packet->fin);
1786 }
1787
1788
1789 /*
1790 * Single-source shortest path search to find the path with the lowest error to
1791 * convert one node's time to another.
1792 * Uses Dijkstra's algorithm
1793 *
1794 * Args:
1795 * fitArray: array with the regression parameters
1796 * traceNum: reference node
1797 * traceNb: number of traces = number of nodes
1798 * distances: array of computed distance from source node to node i,
1799 * INFINITY if i is unreachable, preallocated to the number of
1800 * nodes
1801 * previousVertex: previous vertex from a node i on the way to the source,
1802 * UINT_MAX if i is not on the way or is the source,
1803 * preallocated to the number of nodes
1804 */
1805 static void shortestPath(Fit* const* const fitArray, const unsigned int
1806 traceNum, const unsigned int traceNb, double* const distances, unsigned
1807 int* const previousVertex)
1808 {
1809 bool* visited;
1810 unsigned int i, j;
1811
1812 visited= malloc(traceNb * sizeof(bool));
1813
1814 for (i= 0; i < traceNb; i++)
1815 {
1816 const Fit* fit;
1817
1818 visited[i]= false;
1819
1820 fit= &fitArray[traceNum][i];
1821 g_debug("fitArray[traceNum= %u][i= %u]->n = %u\n", traceNum, i, fit->n);
1822 if (fit->n > 0)
1823 {
1824 distances[i]= fit->e;
1825 previousVertex[i]= traceNum;
1826 }
1827 else
1828 {
1829 distances[i]= INFINITY;
1830 previousVertex[i]= UINT_MAX;
1831 }
1832 }
1833 visited[traceNum]= true;
1834
1835 for (j= 0; j < traceNb; j++)
1836 {
1837 g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]);
1838 }
1839 g_debug("\n");
1840
1841 for (i= 0; i < traceNb - 2; i++)
1842 {
1843 unsigned int v;
1844 double dvMin;
1845
1846 dvMin= INFINITY;
1847 for (j= 0; j < traceNb; j++)
1848 {
1849 if (visited[j] == false && distances[j] < dvMin)
1850 {
1851 v= j;
1852 dvMin= distances[j];
1853 }
1854 }
1855
1856 g_debug("v= %u dvMin= %g\n", v, dvMin);
1857
1858 if (dvMin != INFINITY)
1859 {
1860 visited[v]= true;
1861
1862 for (j= 0; j < traceNb; j++)
1863 {
1864 const Fit* fit;
1865
1866 fit= &fitArray[v][j];
1867 if (visited[j] == false && fit->n > 0 && distances[v] + fit->e
1868 < distances[j])
1869 {
1870 distances[j]= distances[v] + fit->e;
1871 previousVertex[j]= v;
1872 }
1873 }
1874 }
1875 else
1876 {
1877 break;
1878 }
1879
1880 for (j= 0; j < traceNb; j++)
1881 {
1882 g_debug("(%d, %u, %g), ", visited[j], previousVertex[j], distances[j]);
1883 }
1884 g_debug("\n");
1885 }
1886
1887 free(visited);
1888 }
1889
1890
1891 /*
1892 * Cummulate the distances between a reference node and the other nodes
1893 * reachable from it in a graph.
1894 *
1895 * Args:
1896 * distances: array of shortest path distances, with UINT_MAX for
1897 * unreachable nodes
1898 * traceNb: number of nodes = number of traces
1899 */
1900 static double sumDistances(const double* const distances, const unsigned int traceNb)
1901 {
1902 unsigned int i;
1903 double result;
1904
1905 result= 0;
1906 for (i= 0; i < traceNb; i++)
1907 {
1908 if (distances[i] != INFINITY)
1909 {
1910 result+= distances[i];
1911 }
1912 }
1913
1914 return result;
1915 }
1916
1917
1918 /*
1919 * Cummulate the time correction factors between two nodes accross a graph
1920 *
1921 * With traceNum i, reference node r:
1922 * tr= (1 + Xri) * ti + D0ri
1923 * = drift * ti + offset
1924 *
1925 * Args:
1926 * fitArray: array with the regression parameters
1927 * previousVertex: previous vertex from a node i on the way to the source,
1928 * UINT_MAX if i is not on the way or is the source,
1929 * preallocated to the number of nodes
1930 * traceNum: end node, the reference depends on previousVertex
1931 * drift: drift factor
1932 * offset: offset factor
1933 */
1934 static void factors(Fit* const* const fitArray, const unsigned int* const
1935 previousVertex, const unsigned int traceNum, double* const drift, double*
1936 const offset, double* const stDev)
1937 {
1938 if (previousVertex[traceNum] == UINT_MAX)
1939 {
1940 *drift= 1.;
1941 *offset= 0.;
1942 *stDev= 0.;
1943 }
1944 else
1945 {
1946 const Fit* fit;
1947 double cummDrift, cummOffset, cummStDev;
1948 unsigned int pv;
1949
1950 pv= previousVertex[traceNum];
1951
1952 fit= &fitArray[pv][traceNum];
1953 factors(fitArray, previousVertex, pv, &cummDrift, &cummOffset, &cummStDev);
1954
1955 *drift= cummDrift * (1 + fit->x);
1956 *offset= cummDrift * fit->d0 + cummOffset;
1957 *stDev= fit->x * cummStDev + fit->e;
1958 }
1959 }
1960
1961
1962 /*
1963 * Calculate the elapsed time between two timeval values
1964 *
1965 * Args:
1966 * end: end time, result is also stored in this structure
1967 * start: start time
1968 */
1969 static void timeDiff(struct timeval* const end, const struct timeval* const start)
1970 {
1971 if (end->tv_usec >= start->tv_usec)
1972 {
1973 end->tv_sec-= start->tv_sec;
1974 end->tv_usec-= start->tv_usec;
1975 }
1976 else
1977 {
1978 end->tv_sec= end->tv_sec - start->tv_sec - 1;
1979 end->tv_usec= end->tv_usec - start->tv_usec + 1e6;
1980 }
1981 }
1982
1983
1984 LTTV_MODULE("sync", "Synchronize traces", \
1985 "Synchronizes a traceset based on the correspondance of network events", \
1986 init, destroy)
LTTng 2.x Viewer (LTTV)
This page took 0.110152 seconds and 4 git commands to generate.