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;
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.
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,
18 // for INFINITY in math.h
19 #define _ISOC99_SOURCE
25 #include <arpa/inet.h>
29 #include <linux/if_ether.h>
31 #include <netinet/in.h>
35 #include <sys/resource.h>
36 #include <sys/socket.h>
39 #include <sys/types.h>
42 #include <lttv/module.h>
43 #include <lttv/option.h>
52 LTT_CHANNEL_NETIF_STATE
;
55 LTT_EVENT_DEV_HARD_START_XMIT_TCP
,
56 LTT_EVENT_DEV_RECEIVE
,
59 LTT_EVENT_NETWORK_IPV4_INTERFACE
;
81 static gboolean optionSync
;
82 static gboolean optionSyncStats
;
83 static char* optionSyncData
;
86 * Module init function
90 g_debug("\t\t\tXXXX sync init\n");
92 LTT_CHANNEL_NET
= g_quark_from_string("net");
93 LTT_CHANNEL_NETIF_STATE
= g_quark_from_string("netif_state");
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");
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");
123 lttv_option_add("sync", '\0', "synchronize the time between tracefiles "
124 "based on network communications", "none", LTTV_OPT_NONE
, &optionSync
,
127 optionSyncStats
= FALSE
;
128 lttv_option_add("sync-stats", '\0', "print statistics about the time "
129 "synchronization", "none", LTTV_OPT_NONE
, &optionSyncStats
, NULL
, NULL
);
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
);
139 * Module unload function
141 static void destroy()
143 g_debug("\t\t\tXXXX sync destroy\n");
145 lttv_option_remove("sync");
146 lttv_option_remove("sync-stats");
147 lttv_option_remove("sync-data");
152 * Calculate a traceset's drift and offset values based on network events
157 void sync_traceset(LttvTracesetContext
* const tsc
)
159 SyncState
* syncState
;
160 struct timeval startTime
, endTime
;
161 struct rusage startUsage
, endUsage
;
164 if (optionSync
== FALSE
)
166 g_debug("Not synchronizing traceset because option is disabled");
172 gettimeofday(&startTime
, 0);
173 getrusage(RUSAGE_SELF
, &startUsage
);
176 // Initialize data structures
177 syncState
= malloc(sizeof(SyncState
));
179 syncState
->traceNb
= lttv_traceset_number(tsc
->ts
);
183 syncState
->stats
= calloc(1, sizeof(Stats
));
188 syncState
->dataFd
= fopen(optionSyncData
, "w");
189 if (syncState
->dataFd
== NULL
)
195 fprintf(syncState
->dataFd
, "%10s %10s %21s %21s %21s\n", "ni", "nj",
196 "timoy", "dji", "eji");
200 registerHooks(syncState
);
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
);
206 unregisterHooks(syncState
);
208 // Finalize the least-squares analysis
209 finalizeLSA(syncState
);
211 // Find a reference node and structure nodes in a graph
212 doGraphProcessing(syncState
);
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
);
220 retval
= fclose(syncState
->dataFd
);
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
);
257 free(syncState
->stats
);
263 gettimeofday(&endTime
, 0);
264 retval
= getrusage(RUSAGE_SELF
, &endUsage
);
266 timeDiff(&endTime
, &startTime
);
267 timeDiff(&endUsage
.ru_utime
, &startUsage
.ru_utime
);
268 timeDiff(&endUsage
.ru_stime
, &startUsage
.ru_stime
);
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
);
279 * Allocate and initialize data structures for synchronizing a traceset.
280 * Register event hooks.
283 * syncState: container for synchronization data.
284 * This function allocates theses members:
293 void registerHooks(SyncState
* const syncState
)
295 unsigned int i
, j
, k
;
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
);
307 syncState
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
308 for (i
= 0; i
< syncState
->traceNb
; i
++)
310 syncState
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
313 syncState
->traceNumTable
= g_hash_table_new(&g_direct_hash
,
316 syncState
->hookListList
= g_array_sized_new(FALSE
, FALSE
, sizeof(GArray
*),
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
++)
324 LttvTraceContext
* tc
;
329 hookList
= g_array_sized_new(FALSE
, FALSE
, sizeof(LttvTraceHook
), hookNb
);
330 g_array_append_val(syncState
->hookListList
, hookList
);
332 tc
= syncState
->tsc
->traces
[i
];
334 g_hash_table_insert(syncState
->traceNumTable
, tc
->t
, (gpointer
) i
);
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
);
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
));
356 g_assert(hookList
->len
- old_len
== 1);
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
);
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
));
371 g_assert(hookList
->len
- old_len
== 1);
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
);
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
));
386 g_assert(hookList
->len
- old_len
== 1);
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
);
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
));
404 g_assert(hookList
->len
- old_len
== 1);
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
,
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
));
420 g_assert(hookList
->len
- old_len
== 1);
423 // Add the hooks to each tracefile's event_by_id hook list
424 for(j
= 0; j
< tc
->tracefiles
->len
; j
++)
426 LttvTracefileContext
* tfc
;
428 tfc
= g_array_index(tc
->tracefiles
, LttvTracefileContext
*, j
);
430 for(k
= 0; k
< hookList
->len
; k
++)
432 LttvTraceHook
* trace_hook
;
434 trace_hook
= &g_array_index(hookList
, LttvTraceHook
, k
);
435 if (trace_hook
->hook_data
!= syncState
)
437 g_assert_not_reached();
439 if (trace_hook
->mdata
== tfc
->tf
->mdata
)
441 lttv_hooks_add(lttv_hooks_by_id_find(tfc
->event_by_id
,
443 trace_hook
->h
, trace_hook
,
453 * Unregister event hooks. Deallocate some data structures that are not needed
454 * anymore after running the hooks.
456 * syncState: container for synchronization data.
457 * This function deallocates theses members:
464 void unregisterHooks(SyncState
* const syncState
)
466 unsigned int i
, j
, k
;
468 // Remove event hooks
469 for(i
= 0; i
< syncState
->traceNb
; i
++)
471 LttvTraceContext
* tc
;
474 tc
= syncState
->tsc
->traces
[i
];
475 hookList
= g_array_index(syncState
->hookListList
, GArray
*, i
);
477 // Remove the hooks from each tracefile's event_by_id hook list
478 for(j
= 0; j
< tc
->tracefiles
->len
; j
++)
480 LttvTracefileContext
* tfc
;
482 tfc
= g_array_index(tc
->tracefiles
, LttvTracefileContext
*, j
);
484 for(k
= 0; k
< hookList
->len
; k
++)
486 LttvTraceHook
* trace_hook
;
488 trace_hook
= &g_array_index(hookList
, LttvTraceHook
, k
);
489 if (trace_hook
->mdata
== tfc
->tf
->mdata
)
491 lttv_hooks_remove_data(lttv_hooks_by_id_find(tfc
->event_by_id
,
492 trace_hook
->id
), trace_hook
->h
, trace_hook
);
497 g_array_free(hookList
, TRUE
);
500 g_array_free(syncState
->hookListList
, TRUE
);
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
);
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.
520 * syncState: container for synchronization data.
522 void finalizeLSA(SyncState
* const syncState
)
528 printf("Individual synchronization factors:\n");
531 for (i
= 0; i
< syncState
->traceNb
; i
++)
533 for (j
= 0; j
< syncState
->traceNb
; j
++)
540 fit
= &syncState
->fitArray
[i
][j
];
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));
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
));
561 for (i
= 0; i
< syncState
->traceNb
; i
++)
563 for (j
= 0; j
< syncState
->traceNb
; j
++)
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
);
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
);
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
589 * syncState: container for synchronization data.
590 * This function allocates these members:
593 void doGraphProcessing(SyncState
* const syncState
)
597 unsigned int* previousVertex
;
599 distances
= malloc(syncState
->traceNb
* sizeof(double));
600 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
601 syncState
->graphList
= g_queue_new();
603 for (i
= 0; i
< syncState
->traceNb
; i
++)
608 // Perform shortest path search
609 g_debug("shortest path trace %d\ndistances: ", i
);
610 shortestPath(syncState
->fitArray
, i
, syncState
->traceNb
, distances
,
613 for (j
= 0; j
< syncState
->traceNb
; j
++)
615 g_debug("%g, ", distances
[j
]);
617 g_debug("\npreviousVertex: ");
618 for (j
= 0; j
< syncState
->traceNb
; j
++)
620 g_debug("%u, ", previousVertex
[j
]);
624 // Group in graphs nodes that have exchanges
625 errorSum
= sumDistances(distances
, syncState
->traceNb
);
626 result
= g_queue_find_custom(syncState
->graphList
, &i
,
632 g_debug("found graph\n");
633 graph
= (Graph
*) result
->data
;
634 if (errorSum
< graph
->errorSum
)
636 g_debug("adding to graph\n");
637 graph
->errorSum
= errorSum
;
638 free(graph
->previousVertex
);
639 graph
->previousVertex
= previousVertex
;
641 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned
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));
656 g_queue_push_tail(syncState
->graphList
, newGraph
);
660 free(previousVertex
);
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.
671 * syncState: container for synchronization data.
672 * This function deallocates:
677 void calculateFactors(SyncState
* const syncState
)
682 // Calculate the resulting offset and drift between each trace and its
684 g_info("Factors:\n");
687 printf("Resulting synchronization factors:\n");
691 for (i
= 0; i
< syncState
->traceNb
; i
++)
695 result
= g_queue_find_custom(syncState
->graphList
, &i
,
700 double drift
, offset
, stDev
;
703 t
= syncState
->tsc
->traces
[i
]->t
;
704 graph
= (Graph
*) result
->data
;
706 g_info("trace %u (%p) graph: reference %u\n", i
, t
, graph
->reference
);
708 for (j
= 0; j
< syncState
->traceNb
; j
++)
710 g_info("%u, ", graph
->previousVertex
[j
]);
714 factors(syncState
->fitArray
, graph
->previousVertex
, i
, &drift
,
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
));
724 if (i
== graph
->reference
)
726 printf("\ttrace %u reference %u previous vertex - "
728 graph
->reference
, stDev
);
732 printf("\ttrace %u reference %u previous vertex %u "
735 graph
->previousVertex
[i
],
740 if (offset
< minOffset
)
747 fprintf(stderr
, "trace: %d\n", i
);
748 g_assert_not_reached();
752 // Adjust all offsets so the lowest one is 0 (no negative offsets)
753 for (i
= 0; i
< syncState
->traceNb
; i
++)
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
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
);
770 printf("\ttrace %u drift= %g offset= %g (%f)\n", i
,
772 tsc_to_uint64(t
->freq_scale
, t
->start_freq
,
777 lttv_traceset_context_compute_time_span(syncState
->tsc
,
778 &syncState
->tsc
->time_span
);
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
);
786 g_queue_foreach(syncState
->graphList
, &graphRemove
, NULL
);
787 g_queue_free(syncState
->graphList
);
789 for (i
= 0; i
< syncState
->traceNb
; i
++)
791 free(syncState
->fitArray
[i
]);
793 free(syncState
->fitArray
);
795 g_hash_table_destroy(syncState
->traceNumTable
);
800 * Lttv hook function that will be called for network events
803 * hook_data: LttvTraceHook* for the type of event that generated the call
804 * call_data: LttvTracefileContext* at the moment of the event
807 * FALSE Always returns FALSE, meaning to keep processing hooks for
810 static gboolean
process_event_by_id(void* hook_data
, void* call_data
)
812 LttvTraceHook
* trace_hook
;
813 LttvTracefileContext
* tfc
;
818 struct marker_info
* info
;
819 SyncState
* syncState
;
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
);
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
));
834 if (info
->name
== LTT_EVENT_DEV_HARD_START_XMIT_TCP
)
840 syncState
->stats
->totOutE
++;
843 outE
= malloc(sizeof(NetEvent
));
849 matchEvents(outE
, syncState
->unMatchedOutE
, syncState
->unMatchedInE
,
850 event
, trace_hook
, offsetof(Packet
, outE
));
852 g_debug("Output event done\n");
854 else if (info
->name
== LTT_EVENT_DEV_RECEIVE
)
861 syncState
->stats
->totRecv
++;
864 protocol
= ltt_event_get_long_unsigned(event
,
865 lttv_trace_get_hook_field(trace_hook
, 1));
867 if (protocol
== ETH_P_IP
)
873 syncState
->stats
->totRecvIp
++;
876 inE
= malloc(sizeof(NetEvent
));
881 inE
->skb
= (void*) (unsigned long)
882 ltt_event_get_long_unsigned(event
,
883 lttv_trace_get_hook_field(trace_hook
, 0));
885 list
= g_hash_table_lookup(syncState
->pendingRecv
, trace
);
886 if (unlikely(list
== NULL
))
888 g_hash_table_insert(syncState
->pendingRecv
, trace
, list
=
891 g_queue_push_head(list
, inE
);
893 g_debug("Adding inE to pendingRecv\n");
900 else if (info
->name
== LTT_EVENT_TCPV4_RCV
)
904 // Search pendingRecv for an event with the same skb
905 prList
= g_hash_table_lookup(syncState
->pendingRecv
, trace
);
906 if (unlikely(prList
== NULL
))
908 g_debug("No pending receive event list for this trace\n");
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
);
922 g_debug("No matching pending receive event found\n");
930 syncState
->stats
->totInE
++;
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
);
937 matchEvents(inE
, syncState
->unMatchedInE
,
938 syncState
->unMatchedOutE
, event
, trace_hook
,
939 offsetof(Packet
, inE
));
941 g_debug("Input event done\n");
945 else if (info
->name
== LTT_EVENT_PKFREE_SKB
)
949 list
= g_hash_table_lookup(syncState
->pendingRecv
, trace
);
950 if (unlikely(list
== NULL
))
952 g_debug("No pending receive event list for this trace\n");
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
);
966 g_debug("No matching pending receive event found, \"shaddow"
973 inE
= (NetEvent
*) result
->data
;
974 g_queue_delete_link(list
, result
);
975 destroyNetEvent(inE
);
977 g_debug("Non-TCP skb\n");
981 else if (info
->name
== LTT_EVENT_NETWORK_IPV4_INTERFACE
)
986 char addressString
[17];
988 name
= ltt_event_get_string(event
, lttv_trace_get_hook_field(trace_hook
,
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
,
995 convertIP(addressString
, address
);
997 g_debug("name \"%s\" address %s up %lld\n", name
, addressString
, up
);
1001 g_debug("<default>\n");
1009 * Implementation of a packet matching algorithm for TCP
1012 * netEvent new event to match
1013 * unMatchedList list of unmatched events of the same type (send or receive)
1015 * unMatchedOppositeList list of unmatched events of the opposite type of
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
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
)
1029 SyncState
* syncState
;
1030 NetEvent
* companionEvent
;
1032 syncState
= (SyncState
*) trace_hook
->hook_data
;
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
;
1065 companionEvent
= g_hash_table_lookup(unMatchedOppositeList
, packet
);
1066 if (companionEvent
!= NULL
)
1068 if (optionSyncStats
)
1070 syncState
->stats
->totPacket
++;
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
);
1077 packet
= companionEvent
->packet
;
1078 *((NetEvent
**) ((void*) packet
+ fieldOffset
))= netEvent
;
1080 // If this packet acknowleges some data ...
1083 uaList
= g_hash_table_lookup(syncState
->unAcked
, &packet
->connKey
);
1086 Packet
* ackedPacket
;
1088 result
= g_queue_find_custom(uaList
, packet
, &packetAckCompare
);
1090 while (result
!= NULL
)
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, ");
1096 ackedPacket
= (Packet
*) result
->data
;
1097 g_queue_delete_link(uaList
, result
);
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
)
1105 g_hash_table_steal(syncState
->unMatchedOutE
, packet
);
1106 destroyPacket(ackedPacket
);
1108 else if (ackedPacket
->outE
== NULL
)
1110 g_hash_table_steal(syncState
->unMatchedInE
, packet
);
1111 destroyPacket(ackedPacket
);
1115 if (optionSyncStats
)
1117 syncState
->stats
->totExchangeEffective
++;
1120 if (packet
->acks
== NULL
)
1122 packet
->acks
= g_queue_new();
1124 else if (optionSyncStats
)
1126 syncState
->stats
->totPacketCummAcked
++;
1129 g_queue_push_tail(packet
->acks
, ackedPacket
);
1132 result
= g_queue_find_custom(uaList
, packet
,
1136 // It might be possible to do an offset calculation
1137 if (packet
->acks
!= NULL
)
1139 if (optionSyncStats
)
1141 syncState
->stats
->totExchangeReal
++;
1144 g_debug("Synchronization calculation, ");
1145 g_debug("%d acked packets - using last one, ",
1146 g_queue_get_length(packet
->acks
));
1148 ackedPacket
= g_queue_peek_tail(packet
->acks
);
1149 if (ackedPacket
->outE
->trace
!= packet
->inE
->trace
||
1150 ackedPacket
->inE
->trace
!= packet
->outE
->trace
)
1152 g_debug("disorganized exchange - discarding, ");
1154 else if (ackedPacket
->outE
->trace
==
1155 ackedPacket
->inE
->trace
)
1157 g_debug("packets from the same trace - discarding, ");
1163 unsigned int ni
, nj
;
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
];
1187 fit
->st2
+= pow(timoy
, 2);
1189 fit
->sd2
+= pow(dji
, 2);
1190 fit
->std
+= timoy
* dji
;
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
);
1201 freq
= syncState
->tsc
->traces
[ni
]->t
->start_freq
*
1202 syncState
->tsc
->traces
[ni
]->t
->freq_scale
;
1204 fprintf(syncState
->dataFd
, "%10u %10u %21.10f %21.10f %21.10f\n", ni
,
1205 nj
, timoy
/ freq
, dji
/ freq
, eji
/ freq
);
1212 if (needsAck(packet
))
1214 if (optionSyncStats
)
1216 syncState
->stats
->totPacketNeedAck
++;
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
);
1224 ConnectionKey
* connKey
;
1226 connKey
= malloc(sizeof(ConnectionKey
));
1227 memcpy(connKey
, &packet
->connKey
, sizeof(ConnectionKey
));
1228 g_hash_table_insert(syncState
->unAcked
, connKey
, uaList
= g_queue_new());
1230 g_queue_push_tail(uaList
, packet
);
1234 destroyPacket(packet
);
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
1242 netEvent
->packet
= packet
;
1243 *((NetEvent
**) ((void*) packet
+ fieldOffset
))= netEvent
;
1245 g_debug("Adding to unmatched event list, ");
1246 g_hash_table_insert(unMatchedList
, packet
, netEvent
);
1252 * Check if a packet is an acknowledge
1258 static bool isAck(const Packet
* const packet
)
1260 if (packet
->ack
== 1)
1272 * Check if a packet is an acknowledge of another packet.
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
1279 static bool isAcking(const Packet
* const ackPacket
, const Packet
* const ackedPacket
)
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
)
1297 * Check if a packet will increment the sequence number, thus needing an
1301 * true if the packet will need an acknowledge
1304 static bool needsAck(const Packet
* const packet
)
1306 if (packet
->syn
|| packet
->fin
|| packet
->tot_len
- packet
->ihl
* 4 -
1307 packet
->doff
* 4 > 0)
1319 * Compare two ConnectionKey structures
1322 * true if each field of the structure is equal
1325 static bool connectionKeyEqual(const ConnectionKey
* const a
, const ConnectionKey
* const b
)
1327 if (a
->saddr
== b
->saddr
&& a
->daddr
== b
->daddr
&& a
->source
==
1328 b
->source
&& a
->dest
== b
->dest
)
1340 * A GDestroyNotify function for g_hash_table_new_full()
1343 * data: GQueue* list[NetEvent]
1345 static void netEventListDestroy(gpointer data
)
1349 list
= (GQueue
*) data
;
1351 g_debug("XXXX netEventListDestroy\n");
1352 g_queue_foreach(list
, &netEventRemove
, NULL
);
1358 * A GFunc for g_queue_foreach()
1361 * data: NetEvent* event
1364 static void netEventRemove(gpointer data
, gpointer user_data
)
1366 destroyNetEvent((NetEvent
*) data
);
1371 * A GHashFunc for g_hash_table_new()
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.
1379 static guint
netEventPacketHash(gconstpointer key
)
1386 a
= p
->connKey
.source
+ (p
->connKey
.dest
<< 16);
1387 b
= p
->connKey
.saddr
;
1388 c
= p
->connKey
.daddr
;
1411 * A GEqualFunc for g_hash_table_new()
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.
1420 * TRUE if both values are equal
1422 static gboolean
netEventPacketEqual(gconstpointer a
, gconstpointer b
)
1424 const Packet
* pA
, * pB
;
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
&&
1450 * A GDestroyNotify function for g_hash_table_new_full()
1455 static void ghtDestroyNetEvent(gpointer data
)
1457 destroyNetEvent((NetEvent
*) data
);
1462 * A GDestroyNotify function for g_hash_table_new_full()
1465 * data: GQueue* list[Packet]
1467 static void packetListDestroy(gpointer data
)
1471 list
= (GQueue
*) data
;
1473 g_debug("XXXX packetListDestroy\n");
1475 g_queue_foreach(list
, &packetRemove
, NULL
);
1481 * A GFunc for g_queue_foreach()
1484 * data Packet*, packet to destroy
1487 static void packetRemove(gpointer data
, gpointer user_data
)
1491 packet
= (Packet
*) data
;
1493 g_debug("XXXX packetRemove\n");
1494 destroyPacket(packet
);
1499 * Free the memory used by a Packet and the memory of all its associated
1502 static void destroyPacket(Packet
* const packet
)
1504 g_debug("XXXX destroyPacket ");
1505 printPacket(packet
);
1520 g_queue_foreach(packet
->acks
, &packetRemove
, NULL
);
1521 g_queue_free(packet
->acks
);
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
1534 static void destroyNetEvent(NetEvent
* const event
)
1536 g_debug("XXXX destroyNetEvent\n");
1539 destroyPacket(event
->packet
);
1549 * A GFunc for g_queue_foreach()
1552 * data Graph*, graph to destroy
1555 static void graphRemove(gpointer data
, gpointer user_data
)
1559 graph
= (Graph
*) data
;
1561 free(graph
->previousVertex
);
1567 * A GCompareFunc for g_queue_find_custom()
1574 * 0 if the two events have the same skb
1576 static gint
netEventSkbCompare(gconstpointer a
, gconstpointer b
)
1578 if (((NetEvent
*) a
)->skb
== ((NetEvent
*) b
)->skb
)
1590 * A GCompareFunc to be used with g_queue_find_custom()
1597 * 0 if the two net events correspond to the send and receive events of the
1600 static gint
netEventPacketCompare(gconstpointer a
, gconstpointer b
)
1604 pA
= ((NetEvent
*) a
)->packet
;
1605 pB
= ((NetEvent
*) b
)->packet
;
1607 if (netEventPacketEqual(a
, b
))
1619 * A GCompareFunc for g_queue_find_custom()
1622 * a Packet* acked packet
1623 * b Packet* ack packet
1628 static gint
packetAckCompare(gconstpointer a
, gconstpointer b
)
1630 if (isAcking(((Packet
*) b
), ((Packet
*) a
)))
1642 * A GCompareFunc for g_queue_find_custom()
1646 * b: unsigned int* traceNum
1649 * 0 if graph contains traceNum
1651 static gint
graphTraceCompare(gconstpointer a
, gconstpointer b
)
1654 unsigned int traceNum
;
1657 traceNum
= *(unsigned int *) b
;
1659 if (graph
->previousVertex
[traceNum
] != UINT_MAX
)
1663 else if (graph
->reference
== traceNum
)
1675 * A GHashFunc for g_hash_table_new()
1677 * 2.4 kernels used tcp_hashfn(),
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);
1686 * and in 2.6 kernels inet_ehashfn() handles connection hashing with the help of
1687 * Jenkins hashing, jhash.h
1689 * This function uses the XOR method.
1692 * key ConnectionKey*
1694 static guint
connectionHash(gconstpointer key
)
1696 ConnectionKey
* connKey
;
1699 connKey
= (ConnectionKey
*) key
;
1701 result
= (connKey
->saddr
^ connKey
->source
) ^ (connKey
->daddr
^ connKey
->dest
);
1702 result
^= result
>> 16;
1703 result
^= result
>> 8;
1710 * A GEqualFunc for g_hash_table_new()
1713 * a, b ConnectionKey*
1716 * TRUE if both values are equal
1718 static gboolean
connectionEqual(gconstpointer a
, gconstpointer b
)
1720 ConnectionKey
* ckA
, * ckB
;
1722 ckA
= (ConnectionKey
*) a
;
1723 ckB
= (ConnectionKey
*) b
;
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
)
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
)
1745 * A GDestroyNotify function for g_hash_table_new_full()
1748 * data: ConnectionKey*
1750 static void connectionDestroy(gpointer data
)
1752 free((ConnectionKey
*) data
);
1757 * Convert an IP address from 32 bit form to dotted quad
1760 * str: A preallocated string of length >= 17
1763 static void convertIP(char* const str
, const uint32_t addr
)
1765 struct in_addr iaddr
;
1767 iaddr
.s_addr
= htonl(addr
);
1768 strcpy(str
, inet_ntoa(iaddr
));
1773 * Print the content of a Packet structure
1775 static void printPacket(const Packet
* const packet
)
1777 char saddr
[17], daddr
[17];
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
,
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
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
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
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
)
1812 visited
= malloc(traceNb
* sizeof(bool));
1814 for (i
= 0; i
< traceNb
; i
++)
1820 fit
= &fitArray
[traceNum
][i
];
1821 g_debug("fitArray[traceNum= %u][i= %u]->n = %u\n", traceNum
, i
, fit
->n
);
1824 distances
[i
]= fit
->e
;
1825 previousVertex
[i
]= traceNum
;
1829 distances
[i
]= INFINITY
;
1830 previousVertex
[i
]= UINT_MAX
;
1833 visited
[traceNum
]= true;
1835 for (j
= 0; j
< traceNb
; j
++)
1837 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
1841 for (i
= 0; i
< traceNb
- 2; i
++)
1847 for (j
= 0; j
< traceNb
; j
++)
1849 if (visited
[j
] == false && distances
[j
] < dvMin
)
1852 dvMin
= distances
[j
];
1856 g_debug("v= %u dvMin= %g\n", v
, dvMin
);
1858 if (dvMin
!= INFINITY
)
1862 for (j
= 0; j
< traceNb
; j
++)
1866 fit
= &fitArray
[v
][j
];
1867 if (visited
[j
] == false && fit
->n
> 0 && distances
[v
] + fit
->e
1870 distances
[j
]= distances
[v
] + fit
->e
;
1871 previousVertex
[j
]= v
;
1880 for (j
= 0; j
< traceNb
; j
++)
1882 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
1892 * Cummulate the distances between a reference node and the other nodes
1893 * reachable from it in a graph.
1896 * distances: array of shortest path distances, with UINT_MAX for
1898 * traceNb: number of nodes = number of traces
1900 static double sumDistances(const double* const distances
, const unsigned int traceNb
)
1906 for (i
= 0; i
< traceNb
; i
++)
1908 if (distances
[i
] != INFINITY
)
1910 result
+= distances
[i
];
1919 * Cummulate the time correction factors between two nodes accross a graph
1921 * With traceNum i, reference node r:
1922 * tr= (1 + Xri) * ti + D0ri
1923 * = drift * ti + offset
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
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
)
1938 if (previousVertex
[traceNum
] == UINT_MAX
)
1947 double cummDrift
, cummOffset
, cummStDev
;
1950 pv
= previousVertex
[traceNum
];
1952 fit
= &fitArray
[pv
][traceNum
];
1953 factors(fitArray
, previousVertex
, pv
, &cummDrift
, &cummOffset
, &cummStDev
);
1955 *drift
= cummDrift
* (1 + fit
->x
);
1956 *offset
= cummDrift
* fit
->d0
+ cummOffset
;
1957 *stDev
= fit
->x
* cummStDev
+ fit
->e
;
1963 * Calculate the elapsed time between two timeval values
1966 * end: end time, result is also stored in this structure
1969 static void timeDiff(struct timeval
* const end
, const struct timeval
* const start
)
1971 if (end
->tv_usec
>= start
->tv_usec
)
1973 end
->tv_sec
-= start
->tv_sec
;
1974 end
->tv_usec
-= start
->tv_usec
;
1978 end
->tv_sec
= end
->tv_sec
- start
->tv_sec
- 1;
1979 end
->tv_usec
= end
->tv_usec
- start
->tv_usec
+ 1e6
;
1984 LTTV_MODULE("sync", "Synchronize traces", \
1985 "Synchronizes a traceset based on the correspondance of network events", \