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
);
47 static void writeAnalysisGraphsPlotsLinReg(FILE* stream
, SyncState
* const
48 syncState
, const unsigned int i
, const unsigned int j
);
50 // Functions specific to this module
51 static void registerAnalysisLinReg() __attribute__((constructor (102)));
53 static void finalizeLSA(SyncState
* const syncState
);
54 static void doGraphProcessing(SyncState
* const syncState
);
55 static GArray
* calculateFactors(SyncState
* const syncState
);
56 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
57 traceNum
, const unsigned int traceNb
, double* const distances
,
58 unsigned int* const previousVertex
);
59 static double sumDistances(const double* const distances
, const unsigned int
61 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
62 previousVertex
, const unsigned int traceNum
, double* const drift
,
63 double* const offset
, double* const stDev
);
65 // Graph-related Glib functions
66 static void gfGraphDestroy(gpointer data
, gpointer user_data
);
67 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
);
70 static AnalysisModule analysisModuleLinReg
= {
72 .initAnalysis
= &initAnalysisLinReg
,
73 .destroyAnalysis
= &destroyAnalysisLinReg
,
75 .analyzeExchange
= &analyzeExchangeLinReg
,
76 .finalizeAnalysis
= &finalizeAnalysisLinReg
,
77 .printAnalysisStats
= &printAnalysisStatsLinReg
,
78 .writeAnalysisGraphsPlots
= &writeAnalysisGraphsPlotsLinReg
,
79 .writeAnalysisGraphsOptions
= NULL
,
84 * Analysis module registering function
86 static void registerAnalysisLinReg()
88 g_queue_push_tail(&analysisModules
, &analysisModuleLinReg
);
93 * Analysis init function
95 * This function is called at the beginning of a synchronization run for a set
98 * Allocate some of the analysis specific data structures
101 * syncState container for synchronization data.
102 * This function allocates these analysisData members:
106 static void initAnalysisLinReg(SyncState
* const syncState
)
109 AnalysisDataLinReg
* analysisData
;
111 analysisData
= malloc(sizeof(AnalysisDataLinReg
));
112 syncState
->analysisData
= analysisData
;
114 analysisData
->fitArray
= malloc(syncState
->traceNb
* sizeof(Fit
*));
115 for (i
= 0; i
< syncState
->traceNb
; i
++)
117 analysisData
->fitArray
[i
]= calloc(syncState
->traceNb
, sizeof(Fit
));
120 if (syncState
->stats
)
122 analysisData
->stDev
= malloc(sizeof(double) * syncState
->traceNb
);
128 * Analysis destroy function
130 * Free the analysis specific data structures
133 * syncState container for synchronization data.
134 * This function deallocates these analysisData members:
139 static void destroyAnalysisLinReg(SyncState
* const syncState
)
142 AnalysisDataLinReg
* analysisData
;
144 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
146 if (analysisData
== NULL
)
151 for (i
= 0; i
< syncState
->traceNb
; i
++)
153 free(analysisData
->fitArray
[i
]);
155 free(analysisData
->fitArray
);
157 g_queue_foreach(analysisData
->graphList
, &gfGraphDestroy
, NULL
);
158 g_queue_free(analysisData
->graphList
);
160 if (syncState
->stats
)
162 free(analysisData
->stDev
);
165 free(syncState
->analysisData
);
166 syncState
->analysisData
= NULL
;
171 * Perform analysis on a series of event pairs.
173 * If one event pair is a packet, an exchange is composed of at least two
174 * packets, one in each direction. There should be a non-negative minimum
175 * "round trip time" (RTT) between the first and last event of the exchange.
176 * This RTT should be as small as possible so these packets should be closely
177 * related in time like a data packet and an acknowledgement packet. If the
178 * events analyzed are such that the minimum RTT can be zero, there's nothing
179 * gained in analyzing exchanges beyond what can already be figured out by
182 * An exchange can also consist of more than two packets, in case one packet
183 * single handedly acknowledges many data packets.
186 * syncState container for synchronization data
187 * packet structure containing the many events
189 static void analyzeExchangeLinReg(SyncState
* const syncState
, Packet
* const packet
)
196 AnalysisDataLinReg
* analysisData
;
198 g_debug("Synchronization calculation, ");
199 g_debug("%d acked packets - using last one, ",
200 g_queue_get_length(packet
->acks
));
202 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
203 ackedPacket
= g_queue_peek_tail(packet
->acks
);
205 // Calculate the intermediate values for the
206 // least-squares analysis
207 dji
= ((double) ackedPacket
->inE
->tsc
- (double) ackedPacket
->outE
->tsc
+
208 (double) packet
->outE
->tsc
- (double) packet
->inE
->tsc
) / 2;
209 eji
= fabs((double) ackedPacket
->inE
->tsc
- (double) ackedPacket
->outE
->tsc
210 - (double) packet
->outE
->tsc
+ (double) packet
->inE
->tsc
) / 2;
211 timoy
= ((double) ackedPacket
->outE
->tsc
+ (double) packet
->inE
->tsc
) / 2;
212 ni
= ackedPacket
->outE
->traceNum
;
213 nj
= ackedPacket
->inE
->traceNum
;
214 fit
= &analysisData
->fitArray
[nj
][ni
];
218 fit
->st2
+= pow(timoy
, 2);
220 fit
->sd2
+= pow(dji
, 2);
221 fit
->std
+= timoy
* dji
;
223 g_debug("intermediate values: dji= %f ti moy= %f "
224 "ni= %u nj= %u fit: n= %u st= %f st2= %f sd= %f "
225 "sd2= %f std= %f, ", dji
, timoy
, ni
, nj
, fit
->n
,
226 fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
231 * Finalize the factor calculations
233 * The least squares analysis is finalized and finds the factors directly
234 * between each pair of traces that had events together. The traces are
235 * aranged in a graph, a reference trace is chosen and the factors between
236 * this reference and every other trace is calculated. Sometimes it is
237 * necessary to use many graphs when there are "islands" of independent
241 * syncState container for synchronization data.
244 * Factors[traceNb] synchronization factors for each trace
246 static GArray
* finalizeAnalysisLinReg(SyncState
* const syncState
)
250 // Finalize the processing
251 finalizeLSA(syncState
);
253 // Find a reference node and structure nodes in a graph
254 doGraphProcessing(syncState
);
256 /* Calculate the resulting offset and drift between each trace and its
259 factors
= calculateFactors(syncState
);
266 * Print statistics related to analysis. Must be called after
270 * syncState container for synchronization data.
272 static void printAnalysisStatsLinReg(SyncState
* const syncState
)
275 AnalysisDataLinReg
* analysisData
;
277 if (!syncState
->stats
)
282 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
284 printf("Linear regression analysis stats:\n");
286 printf("\tIndividual synchronization factors:\n");
288 for (j
= 0; j
< syncState
->traceNb
; j
++)
290 for (i
= 0; i
< j
; i
++)
294 fit
= &analysisData
->fitArray
[j
][i
];
295 printf("\t\t%3d - %-3d: ", i
, j
);
296 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
297 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
299 fit
= &analysisData
->fitArray
[i
][j
];
300 printf("\t\t%3d - %-3d: ", j
, i
);
301 printf("a0= % 7g a1= 1 %c %7g accuracy %7g\n", fit
->d0
, fit
->x
<
302 0. ? '-' : '+', fabs(fit
->x
), fit
->e
);
307 for (i
= 0; i
< syncState
->traceNb
; i
++)
311 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
312 &gcfGraphTraceCompare
);
317 graph
= (Graph
*) result
->data
;
319 printf("\t\ttrace %u reference %u previous vertex ", i
,
322 if (i
== graph
->reference
)
328 printf("%u ", graph
->previousVertex
[i
]);
331 printf("stdev= %g\n", analysisData
->stDev
[i
]);
335 g_error("Trace %d not part of a graph\n", i
);
342 * Finalize the least-squares analysis. The intermediate values in the fit
343 * array are used to calculate the drift and the offset between each pair of
344 * nodes based on their exchanges.
347 * syncState: container for synchronization data.
349 static void finalizeLSA(SyncState
* const syncState
)
352 AnalysisDataLinReg
* analysisData
;
354 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
356 for (i
= 0; i
< syncState
->traceNb
; i
++)
358 for (j
= 0; j
< syncState
->traceNb
; j
++)
365 fit
= &analysisData
->fitArray
[i
][j
];
367 delta
= fit
->n
* fit
->st2
- pow(fit
->st
, 2);
368 fit
->x
= (fit
->n
* fit
->std
- fit
->st
* fit
->sd
) / delta
;
369 fit
->d0
= (fit
->st2
* fit
->sd
- fit
->st
* fit
->std
) / delta
;
370 fit
->e
= sqrt((fit
->sd2
- (fit
->n
* pow(fit
->std
, 2) +
371 pow(fit
->sd
, 2) * fit
->st2
- 2 * fit
->st
* fit
->sd
372 * fit
->std
) / delta
) / (fit
->n
- 2));
374 g_debug("[i= %u j= %u]\n", i
, j
);
375 g_debug("n= %d st= %g st2= %g sd= %g sd2= %g std= %g\n",
376 fit
->n
, fit
->st
, fit
->st2
, fit
->sd
, fit
->sd2
, fit
->std
);
377 g_debug("xij= %g d0ij= %g e= %g\n", fit
->x
, fit
->d0
, fit
->e
);
378 g_debug("(xji= %g d0ji= %g)\n", -fit
->x
/ (1 + fit
->x
),
379 -fit
->d0
/ (1 + fit
->x
));
387 * Structure nodes in graphs of nodes that had exchanges. Each graph has a
388 * reference node, the one that can reach the others with the smallest
392 * syncState: container for synchronization data.
393 * This function allocates these analysisData members:
396 static void doGraphProcessing(SyncState
* const syncState
)
400 unsigned int* previousVertex
;
401 AnalysisDataLinReg
* analysisData
;
403 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
405 distances
= malloc(syncState
->traceNb
* sizeof(double));
406 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
407 analysisData
->graphList
= g_queue_new();
409 for (i
= 0; i
< syncState
->traceNb
; i
++)
414 // Perform shortest path search
415 g_debug("shortest path trace %d\ndistances: ", i
);
416 shortestPath(analysisData
->fitArray
, i
, syncState
->traceNb
, distances
,
419 for (j
= 0; j
< syncState
->traceNb
; j
++)
421 g_debug("%g, ", distances
[j
]);
423 g_debug("\npreviousVertex: ");
424 for (j
= 0; j
< syncState
->traceNb
; j
++)
426 g_debug("%u, ", previousVertex
[j
]);
430 // Group in graphs nodes that have exchanges
431 errorSum
= sumDistances(distances
, syncState
->traceNb
);
432 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
433 &gcfGraphTraceCompare
);
438 g_debug("found graph\n");
439 graph
= (Graph
*) result
->data
;
440 if (errorSum
< graph
->errorSum
)
442 g_debug("adding to graph\n");
443 graph
->errorSum
= errorSum
;
444 free(graph
->previousVertex
);
445 graph
->previousVertex
= previousVertex
;
447 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned
455 g_debug("creating new graph\n");
456 newGraph
= malloc(sizeof(Graph
));
457 newGraph
->errorSum
= errorSum
;
458 newGraph
->previousVertex
= previousVertex
;
459 newGraph
->reference
= i
;
460 previousVertex
= malloc(syncState
->traceNb
* sizeof(unsigned int));
462 g_queue_push_tail(analysisData
->graphList
, newGraph
);
466 free(previousVertex
);
472 * Calculate the resulting offset and drift between each trace and its
476 * syncState: container for synchronization data.
479 * Factors[traceNb] synchronization factors for each trace
481 static GArray
* calculateFactors(SyncState
* const syncState
)
484 AnalysisDataLinReg
* analysisData
;
487 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
488 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
490 g_array_set_size(factors
, syncState
->traceNb
);
492 // Calculate the resulting offset and drift between each trace and its
494 for (i
= 0; i
< syncState
->traceNb
; i
++)
498 result
= g_queue_find_custom(analysisData
->graphList
, &i
,
499 &gcfGraphTraceCompare
);
504 Factors
* traceFactors
;
506 graph
= (Graph
*) result
->data
;
507 traceFactors
= &g_array_index(factors
, Factors
, i
);
509 reduceFactors(analysisData
->fitArray
, graph
->previousVertex
, i
,
510 &traceFactors
->drift
, &traceFactors
->offset
, &stDev
);
512 if (syncState
->stats
)
514 analysisData
->stDev
[i
]= stDev
;
519 g_error("Trace %d not part of a graph\n", i
);
528 * Single-source shortest path search to find the path with the lowest error to
529 * convert one node's time to another.
530 * Uses Dijkstra's algorithm
533 * fitArray: array with the regression parameters
534 * traceNum: reference node
535 * traceNb: number of traces = number of nodes
536 * distances: array of computed distance from source node to node i,
537 * INFINITY if i is unreachable, preallocated to the number of
539 * previousVertex: previous vertex from a node i on the way to the source,
540 * UINT_MAX if i is not on the way or is the source,
541 * preallocated to the number of nodes
543 static void shortestPath(Fit
* const* const fitArray
, const unsigned int
544 traceNum
, const unsigned int traceNb
, double* const distances
, unsigned
545 int* const previousVertex
)
550 visited
= malloc(traceNb
* sizeof(bool));
552 for (i
= 0; i
< traceNb
; i
++)
558 fit
= &fitArray
[traceNum
][i
];
559 g_debug("fitArray[traceNum= %u][i= %u]->n = %u\n", traceNum
, i
, fit
->n
);
562 distances
[i
]= fit
->e
;
563 previousVertex
[i
]= traceNum
;
567 distances
[i
]= INFINITY
;
568 previousVertex
[i
]= UINT_MAX
;
571 visited
[traceNum
]= true;
573 for (j
= 0; j
< traceNb
; j
++)
575 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
579 for (i
= 0; i
< traceNb
- 2; i
++)
585 for (j
= 0; j
< traceNb
; j
++)
587 if (visited
[j
] == false && distances
[j
] < dvMin
)
594 g_debug("v= %u dvMin= %g\n", v
, dvMin
);
596 if (dvMin
!= INFINITY
)
600 for (j
= 0; j
< traceNb
; j
++)
604 fit
= &fitArray
[v
][j
];
605 if (visited
[j
] == false && fit
->n
> 0 && distances
[v
] + fit
->e
608 distances
[j
]= distances
[v
] + fit
->e
;
609 previousVertex
[j
]= v
;
618 for (j
= 0; j
< traceNb
; j
++)
620 g_debug("(%d, %u, %g), ", visited
[j
], previousVertex
[j
], distances
[j
]);
630 * Cummulate the distances between a reference node and the other nodes
631 * reachable from it in a graph.
634 * distances: array of shortest path distances, with UINT_MAX for
636 * traceNb: number of nodes = number of traces
638 static double sumDistances(const double* const distances
, const unsigned int traceNb
)
644 for (i
= 0; i
< traceNb
; i
++)
646 if (distances
[i
] != INFINITY
)
648 result
+= distances
[i
];
657 * Cummulate the time correction factors between two nodes accross a graph
659 * With traceNum i, reference node r:
660 * tr= (1 + Xri) * ti + D0ri
661 * = drift * ti + offset
664 * fitArray: array with the regression parameters
665 * previousVertex: previous vertex from a node i on the way to the source,
666 * UINT_MAX if i is not on the way or is the source,
667 * preallocated to the number of nodes
668 * traceNum: end node, the reference depends on previousVertex
669 * drift: drift factor
670 * offset: offset factor
672 static void reduceFactors(Fit
* const* const fitArray
, const unsigned int* const
673 previousVertex
, const unsigned int traceNum
, double* const drift
, double*
674 const offset
, double* const stDev
)
676 if (previousVertex
[traceNum
] == UINT_MAX
)
685 double cummDrift
, cummOffset
, cummStDev
;
688 pv
= previousVertex
[traceNum
];
690 fit
= &fitArray
[pv
][traceNum
];
691 reduceFactors(fitArray
, previousVertex
, pv
, &cummDrift
, &cummOffset
,
694 *drift
= cummDrift
* (1 + fit
->x
);
695 *offset
= cummDrift
* fit
->d0
+ cummOffset
;
696 *stDev
= fit
->x
* cummStDev
+ fit
->e
;
702 * A GFunc for g_queue_foreach()
705 * data Graph*, graph to destroy
708 static void gfGraphDestroy(gpointer data
, gpointer user_data
)
712 graph
= (Graph
*) data
;
714 free(graph
->previousVertex
);
720 * A GCompareFunc for g_queue_find_custom()
724 * b: unsigned int* traceNum
727 * 0 if graph contains traceNum
729 static gint
gcfGraphTraceCompare(gconstpointer a
, gconstpointer b
)
732 unsigned int traceNum
;
735 traceNum
= *(unsigned int *) b
;
737 if (graph
->previousVertex
[traceNum
] != UINT_MAX
)
741 else if (graph
->reference
== traceNum
)
753 * Write the analysis-specific graph lines in the gnuplot script.
756 * stream: stream where to write the data
757 * syncState: container for synchronization data
758 * i: first trace number, on the x axis
759 * j: second trace number, garanteed to be larger than i
761 void writeAnalysisGraphsPlotsLinReg(FILE* stream
, SyncState
* const syncState
,
762 const unsigned int i
, const unsigned int j
)
764 AnalysisDataLinReg
* analysisData
;
767 analysisData
= (AnalysisDataLinReg
*) syncState
->analysisData
;
768 fit
= &analysisData
->fitArray
[j
][i
];
772 "title \"Linreg conversion\" with lines "
773 "linecolor rgb \"gray60\" linetype 1, \\\n",
774 fit
->d0
, 1. + fit
->x
);