1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
4 * This program is free software: you can redistribute it and/or modify it
5 * under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation, either version 2.1 of the License, or (at
7 * your option) any later version.
9 * This program is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
12 * License for more details.
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 #define _ISOC99_SOURCE
32 #include "sync_chain.h"
34 #include "event_analysis_chull.h"
51 // Functions common to all analysis modules
52 static void initAnalysisCHull(SyncState
* const syncState
);
53 static void destroyAnalysisCHull(SyncState
* const syncState
);
55 static void analyzeMessageCHull(SyncState
* const syncState
, Message
* const
57 static AllFactors
* finalizeAnalysisCHull(SyncState
* const syncState
);
58 static void printAnalysisStatsCHull(SyncState
* const syncState
);
59 static void writeAnalysisGraphsPlotsCHull(SyncState
* const syncState
, const
60 unsigned int i
, const unsigned int j
);
62 // Functions specific to this module
63 static void openGraphFiles(SyncState
* const syncState
);
64 static void closeGraphFiles(SyncState
* const syncState
);
65 static void writeGraphFiles(SyncState
* const syncState
);
66 static void gfDumpHullToFile(gpointer data
, gpointer userData
);
68 static void grahamScan(GQueue
* const hull
, Point
* const newPoint
, const
70 static int jointCmp(const Point
* const p1
, const Point
* const p2
, const Point
*
71 const p3
) __attribute__((pure
));
72 static double crossProductK(const Point
const* p1
, const Point
const* p2
,
73 const Point
const* p3
, const Point
const* p4
) __attribute__((pure
));
74 static Factors
* calculateFactorsExact(GQueue
* const cu
, GQueue
* const cl
, const
75 LineType lineType
) __attribute__((pure
));
76 static void calculateFactorsFallback(GQueue
* const cr
, GQueue
* const cs
,
77 PairFactors
* const result
);
78 static double slope(const Point
* const p1
, const Point
* const p2
)
79 __attribute__((pure
));
80 static double intercept(const Point
* const p1
, const Point
* const p2
)
81 __attribute__((pure
));
82 static double verticalDistance(Point
* p1
, Point
* p2
, Point
* const point
)
83 __attribute__((pure
));
85 static void gfPointDestroy(gpointer data
, gpointer userData
);
88 static AnalysisModule analysisModuleCHull
= {
90 .initAnalysis
= &initAnalysisCHull
,
91 .destroyAnalysis
= &destroyAnalysisCHull
,
92 .analyzeMessage
= &analyzeMessageCHull
,
93 .finalizeAnalysis
= &finalizeAnalysisCHull
,
94 .printAnalysisStats
= &printAnalysisStatsCHull
,
96 .writeTraceTraceForePlots
= &writeAnalysisGraphsPlotsCHull
,
102 * Analysis module registering function
104 void registerAnalysisCHull()
106 g_queue_push_tail(&analysisModules
, &analysisModuleCHull
);
111 * Analysis init function
113 * This function is called at the beginning of a synchronization run for a set
116 * Allocate some of the analysis specific data structures
119 * syncState container for synchronization data.
120 * This function allocates or initializes these analysisData
125 static void initAnalysisCHull(SyncState
* const syncState
)
128 AnalysisDataCHull
* analysisData
;
130 analysisData
= malloc(sizeof(AnalysisDataCHull
));
131 syncState
->analysisData
= analysisData
;
133 analysisData
->hullArray
= malloc(syncState
->traceNb
* sizeof(GQueue
**));
134 for (i
= 0; i
< syncState
->traceNb
; i
++)
136 analysisData
->hullArray
[i
]= malloc(syncState
->traceNb
* sizeof(GQueue
*));
138 for (j
= 0; j
< syncState
->traceNb
; j
++)
140 analysisData
->hullArray
[i
][j
]= g_queue_new();
144 if (syncState
->stats
)
146 analysisData
->stats
= malloc(sizeof(AnalysisStatsCHull
));
147 analysisData
->stats
->dropped
= 0;
148 analysisData
->stats
->allFactors
= NULL
;
151 if (syncState
->graphsStream
)
153 analysisData
->graphsData
= malloc(sizeof(AnalysisGraphsDataCHull
));
154 openGraphFiles(syncState
);
155 analysisData
->graphsData
->allFactors
= NULL
;
161 * Create and open files used to store convex hull points to genereate
162 * graphs. Allocate and populate array to store file pointers.
165 * syncState: container for synchronization data
167 static void openGraphFiles(SyncState
* const syncState
)
173 AnalysisDataCHull
* analysisData
;
175 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
177 cwd
= changeToGraphsDir(syncState
->graphsDir
);
179 analysisData
->graphsData
->hullPoints
= malloc(syncState
->traceNb
*
181 for (i
= 0; i
< syncState
->traceNb
; i
++)
183 analysisData
->graphsData
->hullPoints
[i
]= malloc(syncState
->traceNb
*
185 for (j
= 0; j
< syncState
->traceNb
; j
++)
189 retval
= snprintf(name
, sizeof(name
),
190 "analysis_chull-%03u_to_%03u.data", j
, i
);
191 if (retval
> sizeof(name
) - 1)
193 name
[sizeof(name
) - 1]= '\0';
195 if ((analysisData
->graphsData
->hullPoints
[i
][j
]= fopen(name
, "w")) ==
198 g_error(strerror(errno
));
207 g_error(strerror(errno
));
214 * Write hull points to files to generate graphs.
217 * syncState: container for synchronization data
219 static void writeGraphFiles(SyncState
* const syncState
)
222 AnalysisDataCHull
* analysisData
;
224 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
226 for (i
= 0; i
< syncState
->traceNb
; i
++)
228 for (j
= 0; j
< syncState
->traceNb
; j
++)
232 g_queue_foreach(analysisData
->hullArray
[i
][j
],
234 analysisData
->graphsData
->hullPoints
[i
][j
]);
242 * A GFunc for g_queue_foreach. Write a hull point to a file used to generate
246 * data: Point*, point to write to the file
247 * userData: FILE*, file pointer where to write the point
249 static void gfDumpHullToFile(gpointer data
, gpointer userData
)
253 point
= (Point
*) data
;
254 fprintf((FILE*) userData
, "%20" PRIu64
" %20" PRIu64
"\n", point
->x
, point
->y
);
259 * Close files used to store convex hull points to generate graphs.
260 * Deallocate array to store file pointers.
263 * syncState: container for synchronization data
265 static void closeGraphFiles(SyncState
* const syncState
)
268 AnalysisDataCHull
* analysisData
;
271 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
273 if (analysisData
->graphsData
->hullPoints
== NULL
)
278 for (i
= 0; i
< syncState
->traceNb
; i
++)
280 for (j
= 0; j
< syncState
->traceNb
; j
++)
284 retval
= fclose(analysisData
->graphsData
->hullPoints
[i
][j
]);
287 g_error(strerror(errno
));
291 free(analysisData
->graphsData
->hullPoints
[i
]);
293 free(analysisData
->graphsData
->hullPoints
);
294 analysisData
->graphsData
->hullPoints
= NULL
;
299 * Analysis destroy function
301 * Free the analysis specific data structures
304 * syncState container for synchronization data.
305 * This function deallocates these analysisData members:
309 static void destroyAnalysisCHull(SyncState
* const syncState
)
312 AnalysisDataCHull
* analysisData
;
314 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
316 if (analysisData
== NULL
)
321 for (i
= 0; i
< syncState
->traceNb
; i
++)
323 for (j
= 0; j
< syncState
->traceNb
; j
++)
325 g_queue_foreach(analysisData
->hullArray
[i
][j
], gfPointDestroy
,
327 g_queue_free(analysisData
->hullArray
[i
][j
]);
329 free(analysisData
->hullArray
[i
]);
331 free(analysisData
->hullArray
);
333 if (syncState
->stats
)
335 freeAllFactors(analysisData
->stats
->allFactors
, syncState
->traceNb
);
337 free(analysisData
->stats
);
340 if (syncState
->graphsStream
)
342 if (analysisData
->graphsData
->hullPoints
!= NULL
)
344 closeGraphFiles(syncState
);
347 freeAllFactors(analysisData
->graphsData
->allFactors
,
350 free(analysisData
->graphsData
);
353 free(syncState
->analysisData
);
354 syncState
->analysisData
= NULL
;
359 * Perform analysis on an event pair.
362 * syncState container for synchronization data
363 * message structure containing the events
365 static void analyzeMessageCHull(SyncState
* const syncState
, Message
* const message
)
367 AnalysisDataCHull
* analysisData
;
372 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
374 newPoint
= malloc(sizeof(Point
));
375 if (message
->inE
->traceNum
< message
->outE
->traceNum
)
377 // CA is inE->traceNum
378 newPoint
->x
= message
->inE
->cpuTime
;
379 newPoint
->y
= message
->outE
->cpuTime
;
381 g_debug("Reception point hullArray[%lu][%lu] "
382 "x= inE->time= %" PRIu64
" y= outE->time= %" PRIu64
,
383 message
->inE
->traceNum
, message
->outE
->traceNum
, newPoint
->x
,
388 // CA is outE->traceNum
389 newPoint
->x
= message
->outE
->cpuTime
;
390 newPoint
->y
= message
->inE
->cpuTime
;
392 g_debug("Send point hullArray[%lu][%lu] "
393 "x= inE->time= %" PRIu64
" y= outE->time= %" PRIu64
,
394 message
->inE
->traceNum
, message
->outE
->traceNum
, newPoint
->x
,
399 analysisData
->hullArray
[message
->inE
->traceNum
][message
->outE
->traceNum
];
401 if (hull
->length
>= 1 && newPoint
->x
< ((Point
*)
402 g_queue_peek_tail(hull
))->x
)
404 if (syncState
->stats
)
406 analysisData
->stats
->dropped
++;
413 grahamScan(hull
, newPoint
, hullType
);
419 * Construct one half of a convex hull from abscissa-sorted points
422 * hull: the points already in the hull
423 * newPoint: a new point to consider
424 * type: which half of the hull to construct
426 static void grahamScan(GQueue
* const hull
, Point
* const newPoint
, const
431 g_debug("grahamScan(hull (length: %u), newPoint, %s)", hull
->length
, type
432 == LOWER
? "LOWER" : "UPPER");
443 if (hull
->length
>= 2)
445 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
448 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
449 g_queue_peek_tail(hull
), newPoint
),
451 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
452 g_queue_peek_tail(hull
), newPoint
) * inversionFactor
);
454 while (hull
->length
>= 2 && jointCmp(g_queue_peek_nth(hull
, hull
->length
-
455 2), g_queue_peek_tail(hull
), newPoint
) * inversionFactor
<= 0)
457 g_debug("Removing hull[%u]", hull
->length
);
458 free((Point
*) g_queue_pop_tail(hull
));
460 if (hull
->length
>= 2)
462 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
465 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
466 g_queue_peek_tail(hull
), newPoint
),
468 jointCmp(g_queue_peek_nth(hull
, hull
->length
- 2),
469 g_queue_peek_tail(hull
), newPoint
) * inversionFactor
);
472 g_queue_push_tail(hull
, newPoint
);
477 * Finalize the factor calculations
480 * syncState container for synchronization data.
483 * AllFactors* synchronization factors for each trace pair, the caller is
484 * responsible for freeing the structure
486 static AllFactors
* finalizeAnalysisCHull(SyncState
* const syncState
)
488 AnalysisDataCHull
* analysisData
;
489 AllFactors
* allFactors
;
491 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
493 if (syncState
->graphsStream
&& analysisData
->graphsData
->hullPoints
!= NULL
)
495 writeGraphFiles(syncState
);
496 closeGraphFiles(syncState
);
499 allFactors
= calculateAllFactors(syncState
);
501 if (syncState
->stats
)
503 allFactors
->refCount
++;
504 analysisData
->stats
->allFactors
= allFactors
;
507 if (syncState
->graphsStream
)
509 allFactors
->refCount
++;
510 analysisData
->graphsData
->allFactors
= allFactors
;
518 * Print statistics related to analysis. Must be called after
522 * syncState container for synchronization data.
524 static void printAnalysisStatsCHull(SyncState
* const syncState
)
526 AnalysisDataCHull
* analysisData
;
529 if (!syncState
->stats
)
534 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
536 printf("Convex hull analysis stats:\n");
537 printf("\tout of order packets dropped from analysis: %u\n",
538 analysisData
->stats
->dropped
);
540 printf("\tNumber of points in convex hulls:\n");
542 for (i
= 0; i
< syncState
->traceNb
; i
++)
544 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
546 printf("\t\t%3d - %-3d: lower half-hull %-5u upper half-hull %-5u\n",
547 i
, j
, analysisData
->hullArray
[j
][i
]->length
,
548 analysisData
->hullArray
[i
][j
]->length
);
552 printf("\tIndividual synchronization factors:\n");
554 for (i
= 0; i
< syncState
->traceNb
; i
++)
556 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
558 PairFactors
* factorsCHull
;
560 factorsCHull
= &analysisData
->stats
->allFactors
->pairFactors
[j
][i
];
561 printf("\t\t%3d - %-3d: %s", i
, j
,
562 approxNames
[factorsCHull
->type
]);
564 if (factorsCHull
->type
== EXACT
)
566 printf(" a0= % 7g a1= 1 %c %7g\n",
567 factorsCHull
->approx
->offset
,
568 factorsCHull
->approx
->drift
< 0. ? '-' : '+',
569 fabs(factorsCHull
->approx
->drift
));
571 else if (factorsCHull
->type
== ACCURATE
)
573 printf("\n\t\t a0: % 7g to % 7g (delta= %7g)\n",
574 factorsCHull
->max
->offset
, factorsCHull
->min
->offset
,
575 factorsCHull
->min
->offset
- factorsCHull
->max
->offset
);
576 printf("\t\t a1: 1 %+7g to %+7g (delta= %7g)\n",
577 factorsCHull
->min
->drift
- 1., factorsCHull
->max
->drift
-
578 1., factorsCHull
->max
->drift
- factorsCHull
->min
->drift
);
580 else if (factorsCHull
->type
== APPROXIMATE
)
582 printf(" a0= % 7g a1= 1 %c %7g error= %7g\n",
583 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
584 - 1. < 0. ? '-' : '+', fabs(factorsCHull
->approx
->drift
-
585 1.), factorsCHull
->accuracy
);
587 else if (factorsCHull
->type
== INCOMPLETE
)
591 if (factorsCHull
->min
->drift
!= -INFINITY
)
593 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
594 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
-
595 1. < 0 ? '-' : '+', fabs(factorsCHull
->min
->drift
-
598 if (factorsCHull
->max
->drift
!= INFINITY
)
600 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
601 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
-
602 1. < 0 ? '-' : '+', fabs(factorsCHull
->max
->drift
-
606 else if (factorsCHull
->type
== SCREWED
)
610 if (factorsCHull
->min
!= NULL
&& factorsCHull
->min
->drift
!= -INFINITY
)
612 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
613 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
-
614 1. < 0 ? '-' : '+', fabs(factorsCHull
->min
->drift
-
617 if (factorsCHull
->max
!= NULL
&& factorsCHull
->max
->drift
!= INFINITY
)
619 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
620 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
-
621 1. < 0 ? '-' : '+', fabs(factorsCHull
->max
->drift
-
625 else if (factorsCHull
->type
== ABSENT
)
631 g_assert_not_reached();
639 * A GFunc for g_queue_foreach()
642 * data Point*, point to destroy
645 static void gfPointDestroy(gpointer data
, gpointer userData
)
649 point
= (Point
*) data
;
655 * Find out if a sequence of three points constitutes a "left turn" or a
659 * p1, p2, p3: The three points.
663 * 0 colinear (unlikely result since this uses floating point
667 static int jointCmp(const Point
const* p1
, const Point
const* p2
, const
671 const double fuzzFactor
= 0.;
673 result
= crossProductK(p1
, p2
, p1
, p3
);
674 g_debug("crossProductK(p1= (%" PRIu64
", %" PRIu64
"), "
675 "p2= (%" PRIu64
", %" PRIu64
"), p1= (%" PRIu64
", %" PRIu64
"), "
676 "p3= (%" PRIu64
", %" PRIu64
"))= %g",
677 p1
->x
, p1
->y
, p2
->x
, p2
->y
, p1
->x
, p1
->y
, p3
->x
, p3
->y
, result
);
678 if (result
< fuzzFactor
)
682 else if (result
> fuzzFactor
)
694 * Calculate the k component of the cross product of two vectors.
697 * p1, p2: start and end points of the first vector
698 * p3, p4: start and end points of the second vector
701 * the k component of the cross product when considering the two vectors to
702 * be in the i-j plane. The direction (sign) of the result can be useful to
703 * determine the relative orientation of the two vectors.
705 static double crossProductK(const Point
const* p1
, const Point
const* p2
,
706 const Point
const* p3
, const Point
const* p4
)
708 return ((double) p2
->x
- p1
->x
) * ((double) p4
->y
- p3
->y
) - ((double)
709 p2
->y
- p1
->y
) * ((double) p4
->x
- p3
->x
);
714 * Analyze the convex hulls to determine the synchronization factors between
715 * each pair of trace.
718 * syncState container for synchronization data.
721 * AllFactors*, see the documentation for the member allFactors of
722 * AnalysisStatsCHull.
724 AllFactors
* calculateAllFactors(SyncState
* const syncState
)
726 unsigned int traceNumA
, traceNumB
;
727 AllFactors
* allFactors
;
728 AnalysisDataCHull
* analysisData
;
730 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
732 // Allocate allFactors and calculate min and max
733 allFactors
= createAllFactors(syncState
->traceNb
);
734 for (traceNumA
= 0; traceNumA
< syncState
->traceNb
; traceNumA
++)
736 for (traceNumB
= 0; traceNumB
< traceNumA
; traceNumB
++)
743 size_t factorsOffset
;
745 {MINIMUM
, offsetof(PairFactors
, min
)},
746 {MAXIMUM
, offsetof(PairFactors
, max
)}
749 cr
= analysisData
->hullArray
[traceNumB
][traceNumA
];
750 cs
= analysisData
->hullArray
[traceNumA
][traceNumB
];
752 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
754 g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= "
755 "hullArray[%u][%u], cs= hullArray[%u][%u], %s)",
756 traceNumA
, traceNumB
, loopValues
[i
].factorsOffset
==
757 offsetof(PairFactors
, min
) ? "min" : "max", traceNumB
,
758 traceNumA
, traceNumA
, traceNumB
, loopValues
[i
].lineType
==
759 MINIMUM
? "MINIMUM" : "MAXIMUM");
760 *((Factors
**) ((void*)
761 &allFactors
->pairFactors
[traceNumA
][traceNumB
] +
762 loopValues
[i
].factorsOffset
))=
763 calculateFactorsExact(cr
, cs
, loopValues
[i
].lineType
);
768 // Calculate approx when possible
769 for (traceNumA
= 0; traceNumA
< syncState
->traceNb
; traceNumA
++)
771 for (traceNumB
= 0; traceNumB
< traceNumA
; traceNumB
++)
773 PairFactors
* factorsCHull
;
775 factorsCHull
= &allFactors
->pairFactors
[traceNumA
][traceNumB
];
776 if (factorsCHull
->min
== NULL
&& factorsCHull
->max
== NULL
)
778 factorsCHull
->type
= APPROXIMATE
;
779 calculateFactorsFallback(analysisData
->hullArray
[traceNumB
][traceNumA
],
780 analysisData
->hullArray
[traceNumA
][traceNumB
],
781 &allFactors
->pairFactors
[traceNumA
][traceNumB
]);
783 else if (factorsCHull
->min
!= NULL
&& factorsCHull
->max
!= NULL
)
785 if (factorsCHull
->min
->drift
!= -INFINITY
&&
786 factorsCHull
->max
->drift
!= INFINITY
)
788 factorsCHull
->type
= ACCURATE
;
789 calculateFactorsMiddle(factorsCHull
);
791 else if (factorsCHull
->min
->drift
!= -INFINITY
||
792 factorsCHull
->max
->drift
!= INFINITY
)
794 factorsCHull
->type
= INCOMPLETE
;
798 factorsCHull
->type
= ABSENT
;
803 //g_assert_not_reached();
804 factorsCHull
->type
= SCREWED
;
813 /* Calculate approximative factors based on minimum and maximum limits. The
814 * best approximation to make is the interior bissector of the angle formed by
815 * the minimum and maximum lines.
817 * The formulae used come from [Haddad, Yoram: Performance dans les systèmes
818 * répartis: des outils pour les mesures, Université de Paris-Sud, Centre
819 * d'Orsay, September 1988] Section 6.1 p.44
821 * The reasoning for choosing this estimator comes from [Duda, A., Harrus, G.,
822 * Haddad, Y., and Bernard, G.: Estimating global time in distributed systems,
823 * Proc. 7th Int. Conf. on Distributed Computing Systems, Berlin, volume 18,
827 * factors: contains the min and max limits, used to store the result
829 void calculateFactorsMiddle(PairFactors
* const factors
)
831 double amin
, amax
, bmin
, bmax
, bhat
;
833 amin
= factors
->max
->offset
;
834 amax
= factors
->min
->offset
;
835 bmin
= factors
->min
->drift
;
836 bmax
= factors
->max
->drift
;
838 g_assert_cmpfloat(bmax
, >=, bmin
);
840 factors
->approx
= malloc(sizeof(Factors
));
841 bhat
= (bmax
* bmin
- 1. + sqrt(1. + pow(bmax
, 2.) * pow(bmin
, 2.) +
842 pow(bmax
, 2.) + pow(bmin
, 2.))) / (bmax
+ bmin
);
843 factors
->approx
->offset
= amax
- (amax
- amin
) / 2. * (pow(bhat
, 2.) + 1.)
844 / (1. + bhat
* bmax
);
845 factors
->approx
->drift
= bhat
;
846 factors
->accuracy
= bmax
- bmin
;
851 * Analyze the convex hulls to determine the minimum or maximum
852 * synchronization factors between one pair of trace.
854 * This implements and improves upon the algorithm in [Haddad, Yoram:
855 * Performance dans les systèmes répartis: des outils pour les mesures,
856 * Université de Paris-Sud, Centre d'Orsay, September 1988] Section 6.2 p.47
858 * Some degenerate cases are possible:
859 * 1) the result is unbounded. In that case, when searching for the maximum
860 * factors, result->drift= INFINITY; result->offset= -INFINITY. When
861 * searching for the minimum factors, it is the opposite. It is not
862 * possible to improve the situation with this data.
863 * 2) no line can be above the upper hull and below the lower hull. This is
864 * because the hulls intersect each other or are reversed. This means that
865 * an assertion was false. Most probably, the clocks are not linear. It is
866 * possible to repeat the search with another algorithm that will find a
867 * "best effort" approximation. See calculateFactorsApprox().
870 * cu: the upper half-convex hull, the line must pass above this
871 * and touch it in one point
872 * cl: the lower half-convex hull, the line must pass below this
873 * and touch it in one point
874 * lineType: search for minimum or maximum factors
877 * If a result is found, a struct Factors is allocated, filed with the
878 * result and returned
879 * NULL otherwise, degenerate case 2 is in effect
881 static Factors
* calculateFactorsExact(GQueue
* const cu
, GQueue
* const cl
, const
887 double inversionFactor
;
890 g_debug("calculateFactorsExact(cu= %p, cl= %p, %s)", cu
, cl
, lineType
==
891 MINIMUM
? "MINIMUM" : "MAXIMUM");
893 if (lineType
== MINIMUM
)
897 inversionFactor
= -1.;
909 // Check for degenerate case 1
910 if (c1
->length
== 0 || c2
->length
== 0 || ((Point
*) g_queue_peek_nth(c1
,
911 i1
))->x
>= ((Point
*) g_queue_peek_nth(c2
, i2
))->x
)
913 result
= malloc(sizeof(Factors
));
914 if (lineType
== MINIMUM
)
916 result
->drift
= -INFINITY
;
917 result
->offset
= INFINITY
;
921 result
->drift
= INFINITY
;
922 result
->offset
= -INFINITY
;
934 g_queue_peek_nth(c1
, i1
),
935 g_queue_peek_nth(c2
, i2
),
936 g_queue_peek_nth(c1
, i1
),
937 g_queue_peek_nth(c2
, i2
- 1)) * inversionFactor
< 0.
940 if (((Point
*) g_queue_peek_nth(c1
, i1
))->x
941 < ((Point
*) g_queue_peek_nth(c2
, i2
- 1))->x
)
953 i1
+ 1 < c1
->length
- 1
955 g_queue_peek_nth(c1
, i1
),
956 g_queue_peek_nth(c2
, i2
),
957 g_queue_peek_nth(c1
, i1
+ 1),
958 g_queue_peek_nth(c2
, i2
)) * inversionFactor
< 0.
961 if (((Point
*) g_queue_peek_nth(c1
, i1
+ 1))->x
962 < ((Point
*) g_queue_peek_nth(c2
, i2
))->x
)
976 g_queue_peek_nth(c1
, i1
),
977 g_queue_peek_nth(c2
, i2
),
978 g_queue_peek_nth(c1
, i1
),
979 g_queue_peek_nth(c2
, i2
- 1)) * inversionFactor
< 0.
982 p1
= g_queue_peek_nth(c1
, i1
);
983 p2
= g_queue_peek_nth(c2
, i2
);
985 g_debug("Resulting points are: c1[i1]: x= %" PRIu64
" y= %" PRIu64
986 " c2[i2]: x= %" PRIu64
" y= %" PRIu64
"", p1
->x
, p1
->y
, p2
->x
, p2
->y
);
988 result
= malloc(sizeof(Factors
));
989 result
->drift
= slope(p1
, p2
);
990 result
->offset
= intercept(p1
, p2
);
992 g_debug("Resulting factors are: drift= %g offset= %g", result
->drift
,
1000 * Analyze the convex hulls to determine approximate synchronization factors
1001 * between one pair of trace when there is no line that can fit in the
1002 * corridor separating them.
1004 * This implements the algorithm in [Ashton, P.: Algorithms for Off-line Clock
1005 * Synchronisation, University of Canterbury, December 1995, 26] Section 4.2.2
1008 * For each point p1 in cr
1009 * For each point p2 in cs
1011 * Calculate the line paramaters
1012 * For each point p3 in each convex hull
1013 * If p3 is on the wrong side of the line
1015 * If error < errorMin
1019 * cr: the upper half-convex hull
1020 * cs: the lower half-convex hull
1021 * result: a pointer to the pre-allocated struct where the results
1024 static void calculateFactorsFallback(GQueue
* const cr
, GQueue
* const cs
,
1025 PairFactors
* const result
)
1027 unsigned int i
, j
, k
;
1032 approx
= malloc(sizeof(Factors
));
1034 for (i
= 0; i
< cs
->length
; i
++)
1036 for (j
= 0; j
< cr
->length
; j
++)
1043 if (((Point
*) g_queue_peek_nth(cs
, i
))->x
< ((Point
*)g_queue_peek_nth(cr
, j
))->x
)
1045 p1
= *(Point
*)g_queue_peek_nth(cs
, i
);
1046 p2
= *(Point
*)g_queue_peek_nth(cr
, j
);
1050 p1
= *(Point
*)g_queue_peek_nth(cr
, j
);
1051 p2
= *(Point
*)g_queue_peek_nth(cs
, i
);
1054 // The lower hull should be above the point
1055 for (k
= 0; k
< cs
->length
; k
++)
1057 if (jointCmp(&p1
, &p2
, g_queue_peek_nth(cs
, k
)) < 0.)
1059 error
+= verticalDistance(&p1
, &p2
, g_queue_peek_nth(cs
, k
));
1063 // The upper hull should be below the point
1064 for (k
= 0; k
< cr
->length
; k
++)
1066 if (jointCmp(&p1
, &p2
, g_queue_peek_nth(cr
, k
)) > 0.)
1068 error
+= verticalDistance(&p1
, &p2
, g_queue_peek_nth(cr
, k
));
1072 if (error
< errorMin
)
1074 g_debug("Fallback: i= %u j= %u is a better match (error= %g)", i
, j
, error
);
1075 approx
->drift
= slope(&p1
, &p2
);
1076 approx
->offset
= intercept(&p1
, &p2
);
1082 result
->approx
= approx
;
1083 result
->accuracy
= errorMin
;
1088 * Calculate the vertical distance between a line and a point
1091 * p1, p2: Two points defining the line
1095 * the vertical distance
1097 static double verticalDistance(Point
* p1
, Point
* p2
, Point
* const point
)
1099 return fabs(slope(p1
, p2
) * point
->x
+ intercept(p1
, p2
) - point
->y
);
1104 * Calculate the slope between two points
1107 * p1, p2 the two points
1112 static double slope(const Point
* const p1
, const Point
* const p2
)
1114 return ((double) p2
->y
- p1
->y
) / (p2
->x
- p1
->x
);
1118 /* Calculate the y-intercept of a line that passes by two points
1121 * p1, p2 the two points
1126 static double intercept(const Point
* const p1
, const Point
* const p2
)
1128 return ((double) p2
->y
* p1
->x
- (double) p1
->y
* p2
->x
) / ((double) p1
->x
- p2
->x
);
1133 * Write the analysis-specific graph lines in the gnuplot script.
1136 * syncState: container for synchronization data
1137 * i: first trace number
1138 * j: second trace number, garanteed to be larger than i
1140 void writeAnalysisGraphsPlotsCHull(SyncState
* const syncState
, const unsigned
1141 int i
, const unsigned int j
)
1143 AnalysisDataCHull
* analysisData
;
1144 PairFactors
* factorsCHull
;
1146 analysisData
= (AnalysisDataCHull
*) syncState
->analysisData
;
1148 fprintf(syncState
->graphsStream
,
1149 "\t\"analysis_chull-%1$03d_to_%2$03d.data\" "
1150 "title \"Lower half-hull\" with linespoints "
1151 "linecolor rgb \"#015a01\" linetype 4 pointtype 8 pointsize 0.8, \\\n"
1152 "\t\"analysis_chull-%2$03d_to_%1$03d.data\" "
1153 "title \"Upper half-hull\" with linespoints "
1154 "linecolor rgb \"#003366\" linetype 4 pointtype 10 pointsize 0.8, \\\n",
1157 factorsCHull
= &analysisData
->graphsData
->allFactors
->pairFactors
[j
][i
];
1158 if (factorsCHull
->type
== EXACT
)
1160 fprintf(syncState
->graphsStream
,
1162 "title \"Exact conversion\" with lines "
1163 "linecolor rgb \"black\" linetype 1, \\\n",
1164 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1166 else if (factorsCHull
->type
== ACCURATE
)
1168 fprintf(syncState
->graphsStream
,
1169 "\t%.2f + %.10f * x "
1170 "title \"Min conversion\" with lines "
1171 "linecolor rgb \"black\" linetype 5, \\\n",
1172 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1173 fprintf(syncState
->graphsStream
,
1174 "\t%.2f + %.10f * x "
1175 "title \"Max conversion\" with lines "
1176 "linecolor rgb \"black\" linetype 8, \\\n",
1177 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1178 fprintf(syncState
->graphsStream
,
1179 "\t%.2f + %.10f * x "
1180 "title \"Middle conversion\" with lines "
1181 "linecolor rgb \"black\" linetype 1, \\\n",
1182 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1184 else if (factorsCHull
->type
== APPROXIMATE
)
1186 fprintf(syncState
->graphsStream
,
1187 "\t%.2f + %.10f * x "
1188 "title \"Fallback conversion\" with lines "
1189 "linecolor rgb \"gray60\" linetype 1, \\\n",
1190 factorsCHull
->approx
->offset
, factorsCHull
->approx
->drift
);
1192 else if (factorsCHull
->type
== INCOMPLETE
)
1194 if (factorsCHull
->min
->drift
!= -INFINITY
)
1196 fprintf(syncState
->graphsStream
,
1197 "\t%.2f + %.10f * x "
1198 "title \"Min conversion\" with lines "
1199 "linecolor rgb \"black\" linetype 5, \\\n",
1200 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1203 if (factorsCHull
->max
->drift
!= INFINITY
)
1205 fprintf(syncState
->graphsStream
,
1206 "\t%.2f + %.10f * x "
1207 "title \"Max conversion\" with lines "
1208 "linecolor rgb \"black\" linetype 8, \\\n",
1209 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1212 else if (factorsCHull
->type
== SCREWED
)
1214 if (factorsCHull
->min
!= NULL
&& factorsCHull
->min
->drift
!= -INFINITY
)
1216 fprintf(syncState
->graphsStream
,
1217 "\t%.2f + %.10f * x "
1218 "title \"Min conversion\" with lines "
1219 "linecolor rgb \"black\" linetype 5, \\\n",
1220 factorsCHull
->min
->offset
, factorsCHull
->min
->drift
);
1223 if (factorsCHull
->max
!= NULL
&& factorsCHull
->max
->drift
!= INFINITY
)
1225 fprintf(syncState
->graphsStream
,
1226 "\t%.2f + %.10f * x "
1227 "title \"Max conversion\" with lines "
1228 "linecolor rgb \"black\" linetype 8, \\\n",
1229 factorsCHull
->max
->offset
, factorsCHull
->max
->drift
);
1232 else if (factorsCHull
->type
== ABSENT
)
1237 g_assert_not_reached();