1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License Version 2 as
6 * published by the Free Software Foundation;
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
19 // for INFINITY in math.h
20 #define _ISOC99_SOURCE
30 #include "sync_chain.h"
32 #include "event_analysis_linreg.h"
36 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
40 // Functions common to all analysis modules
41 static void initAnalysisLinReg(SyncState
* const syncState
);
42 static void destroyAnalysisLinReg(SyncState
* const syncState
);
44 static void analyzeExchangeLinReg(SyncState
* const syncState
, Packet
* const packet
);
45 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
);
46 static void printAnalysisStatsLinReg(SyncState
* const syncState
);
48 // Functions specific to this module
49 static void registerAnalysisLinReg() __attribute__((constructor (101)));
51 static void finalizeLSA(SyncState
* const syncState
);
52 static void doGraphProcessing(SyncState
* const syncState
);
53 static GArray
* calculateFactors(SyncState
* const syncState
);
54 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
55 traceNum
, const unsigned int traceNb
, double* const distances
,
56 unsigned int* const previousVertex
);
57 static double sumDistances(const double* const distances
, const unsigned int
59 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
60 previousVertex
, const unsigned int traceNum
, double* const drift
,
61 double* const offset
, double* const stDev
);
63 // Graph-related Glib functions
64 static void gfGraphDestroy(gpointer data
, gpointer user_data
);
65 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
);
68 static AnalysisModule analysisModuleLinReg
= {
70 .initAnalysis
= &initAnalysisLinReg
,
71 .destroyAnalysis
= &destroyAnalysisLinReg
,
73 .analyzeExchange
= &analyzeExchangeLinReg
,
74 .finalizeAnalysis
= &finalizeAnalysisLinReg
,
75 .printAnalysisStats
= &printAnalysisStatsLinReg
,
80 * Analysis module registering function
82 static void registerAnalysisLinReg()
84 g_queue_push_tail(&analysisModules
, &analysisModuleLinReg
);
89 * Analysis init function
91 * This function is called at the beginning of a synchronization run for a set
94 * Allocate some of the analysis specific data structures
97 * syncState container for synchronization data.
98 * This function allocates these analysisData members:
102 static void initAnalysisLinReg(SyncState
* const syncState
)
105 AnalysisDataLinReg
* analysisData
;
107 analysisData
= malloc(sizeof(AnalysisDataLinReg
));
108 syncState
->analysisData
= analysisData
;
110 analysisData
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
111 for (i
= 0; i
< syncState
->traceNb
; i
++)
113 analysisData
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
116 if (syncState
->stats
)
118 analysisData
->stDev
= malloc(sizeof(double) * syncState
->traceNb
);
124 * Analysis destroy function
126 * Free the analysis specific data structures
129 * syncState container for synchronization data.
130 * This function deallocates these analysisData members:
135 static void destroyAnalysisLinReg(SyncState
* const syncState
)
138 AnalysisDataLinReg
* analysisData
;
140 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
142 if (analysisData
== NULL
)
147 for (i
= 0; i
< syncState
->traceNb
; i
++)
149 free(analysisData
->fitArray
[i
]);
151 free(analysisData
->fitArray
);
153 g_queue_foreach(analysisData
->graphList
, &gfGraphDestroy
, NULL
);
154 g_queue_free(analysisData
->graphList
);
156 if (syncState
->stats
)
158 free(analysisData
->stDev
);
161 free(syncState
->analysisData
);
162 syncState
->analysisData
= NULL
;
167 * Perform analysis on a series of event pairs.
169 * If one event pair is a packet, an exchange is composed of at least two
170 * packets, one in each direction. There should be a non-negative minimum
171 * "round trip time" (RTT) between the first and last event of the exchange.
172 * This RTT should be as small as possible so these packets should be closely
173 * related in time like a data packet and an acknowledgement packet. If the
174 * events analyzed are such that the minimum RTT can be zero, there's nothing
175 * gained in analyzing exchanges beyond what can already be figured out by
178 * An exchange can also consist of more than two packets, in case one packet
179 * single handedly acknowledges many data packets.
182 * syncState container for synchronization data
183 * packet structure containing the many events
185 static void analyzeExchangeLinReg(SyncState
* const syncState
, Packet
* const packet
)
192 AnalysisDataLinReg
* analysisData
;
194 g_debug("Synchronization calculation, ");
195 g_debug("%d acked packets - using last one, ",
196 g_queue_get_length(packet
->acks
));
198 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
199 ackedPacket
= g_queue_peek_tail(packet
->acks
);
201 // Calculate the intermediate values for the
202 // least-squares analysis
203 dji
= ((double) ackedPacket
->inE
->tsc
- (double) ackedPacket
->outE
->tsc
+
204 (double) packet
->outE
->tsc
- (double) packet
->inE
->tsc
) / 2;
205 eji
= fabs((double) ackedPacket
->inE
->tsc
- (double) ackedPacket
->outE
->tsc
206 - (double) packet
->outE
->tsc
+ (double) packet
->inE
->tsc
) / 2;
207 timoy
= ((double) ackedPacket
->outE
->tsc
+ (double) packet
->inE
->tsc
) / 2;
208 ni
= ackedPacket
->outE
->traceNum
;
209 nj
= ackedPacket
->inE
->traceNum
;
210 fit
= &analysisData
->fitArray
[nj
][ni
];
214 fit
->st2
+= pow(timoy
, 2);
216 fit
->sd2
+= pow(dji
, 2);
217 fit
->std
+= timoy
* dji
;
219 g_debug("intermediate values: dji= %f ti moy= %f "
220 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
221 "sd2= %f std= %f, ", dji
, timoy
, ni
, nj
, fit
->n
,
222 fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
227 * Finalize the factor calculations
229 * The least squares analysis is finalized and finds the factors directly
230 * between each pair of traces that had events together. The traces are
231 * aranged in a graph, a reference trace is chosen and the factors between
232 * this reference and every other trace is calculated. Sometimes it is
233 * necessary to use many graphs when there are "islands" of independent
237 * syncState container for synchronization data.
240 * Factors[traceNb] synchronization factors for each trace
242 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
)
246 // Finalize the processing
247 finalizeLSA(syncState
);
249 // Find a reference node and structure nodes in a graph
250 doGraphProcessing(syncState
);
252 /* Calculate the resulting offset and drift between each trace and its
255 factors
= calculateFactors(syncState
);
262 * Print statistics related to analysis. Must be called after
266 * syncState container for synchronization data.
268 static void printAnalysisStatsLinReg(SyncState
* const syncState
)
271 AnalysisDataLinReg
* analysisData
;
273 if (!syncState
->stats
)
278 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
280 printf("Linear regression analysis stats:\n");
282 printf("\tIndividual synchronization factors:\n");
284 for (j
= 0; j
< syncState
->traceNb
; j
++)
286 for (i
= 0; i
< j
; i
++)
290 fit
= &analysisData
->fitArray
[j
][i
];
291 printf("\t\t%3d - %-3d: ", i
, j
);
292 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
293 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
295 fit
= &analysisData
->fitArray
[i
][j
];
296 printf("\t\t%3d - %-3d: ", j
, i
);
297 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
298 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
303 for (i
= 0; i
< syncState
->traceNb
; i
++)
307 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
308 &gcfGraphTraceCompare
);
313 graph
= (Graph
*) result
->data
;
315 printf("\t\ttrace %u reference %u previous vertex ", i
,
318 if (i
== graph
->reference
)
324 printf("%u ", graph
->previousVertex
[i
]);
327 printf("stdev= %g\n", analysisData
->stDev
[i
]);
331 g_error("Trace %d not part of a graph\n", i
);
338 * Finalize the least-squares analysis. The intermediate values in the fit
339 * array are used to calculate the drift and the offset between each pair of
340 * nodes based on their exchanges.
343 * syncState: container for synchronization data.
345 static void finalizeLSA(SyncState
* const syncState
)
348 AnalysisDataLinReg
* analysisData
;
350 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
352 for (i
= 0; i
< syncState
->traceNb
; i
++)
354 for (j
= 0; j
< syncState
->traceNb
; j
++)
361 fit
= &analysisData
->fitArray
[i
][j
];
363 delta
= fit
->n
* fit
->st2
- pow(fit
->st
, 2);
364 fit
->x
= (fit
->n
* fit
->std
- fit
->st
* fit
->sd
) / delta
;
365 fit
->d0
= (fit
->st2
* fit
->sd
- fit
->st
* fit
->std
) / delta
;
366 fit
->e
= sqrt((fit
->sd2
- (fit
->n
* pow(fit
->std
, 2) +
367 pow(fit
->sd
, 2) * fit
->st2
- 2 * fit
->st
* fit
->sd
368 * fit
->std
) / delta
) / (fit
->n
- 2));
370 g_debug("[i= %u j= %u]\n", i
, j
);
371 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g\n",
372 fit
->n
, fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
373 g_debug("xij= %g d0ij= %g e= %g\n", fit
->x
, fit
->d0
, fit
->e
);
374 g_debug("(xji= %g d0ji= %g)\n", -fit
->x
/ (1 + fit
->x
),
375 -fit
->d0
/ (1 + fit
->x
));
383 * Structure nodes in graphs of nodes that had exchanges. Each graph has a
384 * reference node, the one that can reach the others with the smallest
388 * syncState: container for synchronization data.
389 * This function allocates these analysisData members:
392 static void doGraphProcessing(SyncState
* const syncState
)
396 unsigned int* previousVertex
;
397 AnalysisDataLinReg
* analysisData
;
399 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
401 distances
= malloc(syncState
->traceNb
* sizeof(double));
402 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
403 analysisData
->graphList
= g_queue_new();
405 for (i
= 0; i
< syncState
->traceNb
; i
++)
410 // Perform shortest path search
411 g_debug("shortest path trace %d\ndistances: ", i
);
412 shortestPath(analysisData
->fitArray
, i
, syncState
->traceNb
, distances
,
415 for (j
= 0; j
< syncState
->traceNb
; j
++)
417 g_debug("%g, ", distances
[j
]);
419 g_debug("\npreviousVertex: ");
420 for (j
= 0; j
< syncState
->traceNb
; j
++)
422 g_debug("%u, ", previousVertex
[j
]);
426 // Group in graphs nodes that have exchanges
427 errorSum
= sumDistances(distances
, syncState
->traceNb
);
428 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
429 &gcfGraphTraceCompare
);
434 g_debug("found graph\n");
435 graph
= (Graph
*) result
->data
;
436 if (errorSum
< graph
->errorSum
)
438 g_debug("adding to graph\n");
439 graph
->errorSum
= errorSum
;
440 free(graph
->previousVertex
);
441 graph
->previousVertex
= previousVertex
;
443 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned
451 g_debug("creating new graph\n");
452 newGraph
= malloc(sizeof(Graph
));
453 newGraph
->errorSum
= errorSum
;
454 newGraph
->previousVertex
= previousVertex
;
455 newGraph
->reference
= i
;
456 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
458 g_queue_push_tail(analysisData
->graphList
, newGraph
);
462 free(previousVertex
);
468 * Calculate the resulting offset and drift between each trace and its
472 * syncState: container for synchronization data.
475 * Factors[traceNb] synchronization factors for each trace
477 static GArray
* calculateFactors(SyncState
* const syncState
)
480 AnalysisDataLinReg
* analysisData
;
483 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
484 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
487 // Calculate the resulting offset and drift between each trace and its
489 for (i
= 0; i
< syncState
->traceNb
; i
++)
493 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
494 &gcfGraphTraceCompare
);
499 Factors
* traceFactors
;
501 graph
= (Graph
*) result
->data
;
502 traceFactors
= &g_array_index(factors
, Factors
, i
);
504 reduceFactors(analysisData
->fitArray
, graph
->previousVertex
, i
,
505 &traceFactors
->drift
, &traceFactors
->offset
, &stDev
);
507 if (syncState
->stats
)
509 analysisData
->stDev
[i
]= stDev
;
514 g_error("Trace %d not part of a graph\n", i
);
523 * Single-source shortest path search to find the path with the lowest error to
524 * convert one node's time to another.
525 * Uses Dijkstra's algorithm
528 * fitArray: array with the regression parameters
529 * traceNum: reference node
530 * traceNb: number of traces = number of nodes
531 * distances: array of computed distance from source node to node i,
532 * INFINITY if i is unreachable, preallocated to the number of
534 * previousVertex: previous vertex from a node i on the way to the source,
535 * UINT_MAX if i is not on the way or is the source,
536 * preallocated to the number of nodes
538 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
539 traceNum
, const unsigned int traceNb
, double* const distances
, unsigned
540 int* const previousVertex
)
545 visited
= malloc(traceNb
* sizeof(bool));
547 for (i
= 0; i
< traceNb
; i
++)
553 fit
= &fitArray
[traceNum
][i
];
554 g_debug("fitArray[traceNum= %u][i= %u]->n = %u\n", traceNum
, i
, fit
->n
);
557 distances
[i
]= fit
->e
;
558 previousVertex
[i
]= traceNum
;
562 distances
[i
]= INFINITY
;
563 previousVertex
[i
]= UINT_MAX
;
566 visited
[traceNum
]= true;
568 for (j
= 0; j
< traceNb
; j
++)
570 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
574 for (i
= 0; i
< traceNb
- 2; i
++)
580 for (j
= 0; j
< traceNb
; j
++)
582 if (visited
[j
] == false && distances
[j
] < dvMin
)
589 g_debug("v= %u dvMin= %g\n", v
, dvMin
);
591 if (dvMin
!= INFINITY
)
595 for (j
= 0; j
< traceNb
; j
++)
599 fit
= &fitArray
[v
][j
];
600 if (visited
[j
] == false && fit
->n
> 0 && distances
[v
] + fit
->e
603 distances
[j
]= distances
[v
] + fit
->e
;
604 previousVertex
[j
]= v
;
613 for (j
= 0; j
< traceNb
; j
++)
615 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
625 * Cummulate the distances between a reference node and the other nodes
626 * reachable from it in a graph.
629 * distances: array of shortest path distances, with UINT_MAX for
631 * traceNb: number of nodes = number of traces
633 static double sumDistances(const double* const distances
, const unsigned int traceNb
)
639 for (i
= 0; i
< traceNb
; i
++)
641 if (distances
[i
] != INFINITY
)
643 result
+= distances
[i
];
652 * Cummulate the time correction factors between two nodes accross a graph
654 * With traceNum i, reference node r:
655 * tr= (1 + Xri) * ti + D0ri
656 * = drift * ti + offset
659 * fitArray: array with the regression parameters
660 * previousVertex: previous vertex from a node i on the way to the source,
661 * UINT_MAX if i is not on the way or is the source,
662 * preallocated to the number of nodes
663 * traceNum: end node, the reference depends on previousVertex
664 * drift: drift factor
665 * offset: offset factor
667 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
668 previousVertex
, const unsigned int traceNum
, double* const drift
, double*
669 const offset
, double* const stDev
)
671 if (previousVertex
[traceNum
] == UINT_MAX
)
680 double cummDrift
, cummOffset
, cummStDev
;
683 pv
= previousVertex
[traceNum
];
685 fit
= &fitArray
[pv
][traceNum
];
686 reduceFactors(fitArray
, previousVertex
, pv
, &cummDrift
, &cummOffset
,
689 *drift
= cummDrift
* (1 + fit
->x
);
690 *offset
= cummDrift
* fit
->d0
+ cummOffset
;
691 *stDev
= fit
->x
* cummStDev
+ fit
->e
;
697 * A GFunc for g_queue_foreach()
700 * data Graph*, graph to destroy
703 static void gfGraphDestroy(gpointer data
, gpointer user_data
)
707 graph
= (Graph
*) data
;
709 free(graph
->previousVertex
);
715 * A GCompareFunc for g_queue_find_custom()
719 * b: unsigned int* traceNum
722 * 0 if graph contains traceNum
724 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
)
727 unsigned int traceNum
;
730 traceNum
= *(unsigned int *) b
;
732 if (graph
->previousVertex
[traceNum
] != UINT_MAX
)
736 else if (graph
->reference
== traceNum
)