projects / lttv.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Add convex hull algorithm-based synchronization
[lttv.git] / lttv / lttv / sync / event_analysis_chull.c
1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
3 *
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;
7 *
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.
12 *
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,
16 * MA 02111-1307, USA.
17 */
18 #define _ISOC99_SOURCE
19
20 #ifdef HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23
24 #include <errno.h>
25 #include <math.h>
26 #include <float.h>
27 #include <stdlib.h>
28 #include <stdio.h>
29 #include <unistd.h>
30
31 #include "sync_chain.h"
32
33 #include "event_analysis_chull.h"
34
35
36 #ifndef g_info
37 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
38 #endif
39
40
41 typedef enum
42 {
43 LOWER,
44 UPPER
45 } HullType;
46
47
48 typedef enum
49 {
50 MINIMUM,
51 MAXIMUM
52 } LineType;
53
54
55 // Functions common to all analysis modules
56 static void initAnalysisCHull(SyncState* const syncState);
57 static void destroyAnalysisCHull(SyncState* const syncState);
58
59 static void analyzePacketCHull(SyncState* const syncState, Packet* const packet);
60 static GArray* finalizeAnalysisCHull(SyncState* const syncState);
61 static void printAnalysisStatsCHull(SyncState* const syncState);
62 static void writeAnalysisGraphsPlotsCHull(FILE* stream, SyncState* const
63 syncState, const unsigned int i, const unsigned int j);
64
65 // Functions specific to this module
66 static void registerAnalysisCHull() __attribute__((constructor (101)));
67
68 static void openGraphFiles(SyncState* const syncState);
69 static void closeGraphFiles(SyncState* const syncState);
70 static void writeGraphFiles(SyncState* const syncState);
71 static void gfDumpHullToFile(gpointer data, gpointer userData);
72
73 static void grahamScan(GQueue* const hull, Point* const newPoint, const
74 HullType type);
75 static int jointCmp(const Point* const p1, const Point* const p2, const Point*
76 const p3) __attribute__((pure));
77 static double crossProductK(const Point const* p1, const Point const* p2,
78 const Point const* p3, const Point const* p4) __attribute__((pure));
79 static FactorsCHull** calculateAllFactors(SyncState* const syncState);
80 static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const
81 LineType lineType) __attribute__((pure));
82 static void calculateFactorsMiddle(FactorsCHull* factors);
83 static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs,
84 FactorsCHull* const result);
85 static double slope(const Point* const p1, const Point* const p2)
86 __attribute__((pure));
87 static double intercept(const Point* const p1, const Point* const p2)
88 __attribute__((pure));
89 static GArray* reduceFactors(SyncState* const syncState, FactorsCHull**
90 allFactors);
91 static void freeAllFactors(const SyncState* const syncState, FactorsCHull**
92 const allFactors);
93 static double verticalDistance(Point* p1, Point* p2, Point* const point)
94 __attribute__((pure));
95 static void floydWarshall(SyncState* const syncState, FactorsCHull** const
96 allFactors, double*** const distances, unsigned int*** const
97 predecessors);
98 static void getFactors(FactorsCHull** const allFactors, unsigned int** const
99 predecessors, unsigned int* const references, const unsigned int traceNum,
100 Factors* const factors);
101
102 static void gfPointDestroy(gpointer data, gpointer userData);
103
104
105 static AnalysisModule analysisModuleCHull= {
106 .name= "chull",
107 .initAnalysis= &initAnalysisCHull,
108 .destroyAnalysis= &destroyAnalysisCHull,
109 .analyzePacket= &analyzePacketCHull,
110 .analyzeExchange= NULL,
111 .finalizeAnalysis= &finalizeAnalysisCHull,
112 .printAnalysisStats= &printAnalysisStatsCHull,
113 .writeAnalysisGraphsPlots= &writeAnalysisGraphsPlotsCHull,
114 .writeAnalysisGraphsOptions= NULL,
115 };
116
117
118 /*
119 * Analysis module registering function
120 */
121 static void registerAnalysisCHull()
122 {
123 g_queue_push_tail(&analysisModules, &analysisModuleCHull);
124 }
125
126
127 /*
128 * Analysis init function
129 *
130 * This function is called at the beginning of a synchronization run for a set
131 * of traces.
132 *
133 * Allocate some of the analysis specific data structures
134 *
135 * Args:
136 * syncState container for synchronization data.
137 * This function allocates or initializes these analysisData
138 * members:
139 * hullArray
140 * dropped
141 */
142 static void initAnalysisCHull(SyncState* const syncState)
143 {
144 unsigned int i, j;
145 AnalysisDataCHull* analysisData;
146
147 analysisData= malloc(sizeof(AnalysisDataCHull));
148 syncState->analysisData= analysisData;
149
150 analysisData->hullArray= malloc(syncState->traceNb * sizeof(GQueue**));
151 for (i= 0; i < syncState->traceNb; i++)
152 {
153 analysisData->hullArray[i]= malloc(syncState->traceNb * sizeof(GQueue*));
154
155 for (j= 0; j < syncState->traceNb; j++)
156 {
157 analysisData->hullArray[i][j]= g_queue_new();
158 }
159 }
160
161 if (syncState->stats)
162 {
163 analysisData->stats= malloc(sizeof(AnalysisStatsCHull));
164 analysisData->stats->dropped= 0;
165 analysisData->stats->allFactors= NULL;
166 }
167
168 if (syncState->graphs)
169 {
170 analysisData->graphsData= malloc(sizeof(AnalysisGraphsDataCHull));
171 openGraphFiles(syncState);
172 analysisData->graphsData->allFactors= NULL;
173 }
174 }
175
176
177 /*
178 * Create and open files used to store convex hull points to genereate
179 * graphs. Allocate and populate array to store file pointers.
180 *
181 * Args:
182 * syncState: container for synchronization data
183 */
184 static void openGraphFiles(SyncState* const syncState)
185 {
186 unsigned int i, j;
187 int retval;
188 char* cwd;
189 char name[31];
190 AnalysisDataCHull* analysisData;
191
192 analysisData= (AnalysisDataCHull*) syncState->analysisData;
193
194 cwd= changeToGraphDir(syncState->graphs);
195
196 analysisData->graphsData->hullPoints= malloc(syncState->traceNb *
197 sizeof(FILE**));
198 for (i= 0; i < syncState->traceNb; i++)
199 {
200 analysisData->graphsData->hullPoints[i]= malloc(syncState->traceNb *
201 sizeof(FILE*));
202 for (j= 0; j < syncState->traceNb; j++)
203 {
204 if (i != j)
205 {
206 retval= snprintf(name, sizeof(name),
207 "analysis_chull-%03u_to_%03u.data", j, i);
208 if (retval > sizeof(name) - 1)
209 {
210 name[sizeof(name) - 1]= '\0';
211 }
212 if ((analysisData->graphsData->hullPoints[i][j]= fopen(name, "w")) ==
213 NULL)
214 {
215 g_error(strerror(errno));
216 }
217 }
218 }
219 }
220
221 retval= chdir(cwd);
222 if (retval == -1)
223 {
224 g_error(strerror(errno));
225 }
226 free(cwd);
227 }
228
229
230 /*
231 * Write hull points to files to generate graphs.
232 *
233 * Args:
234 * syncState: container for synchronization data
235 */
236 static void writeGraphFiles(SyncState* const syncState)
237 {
238 unsigned int i, j;
239 AnalysisDataCHull* analysisData;
240
241 analysisData= (AnalysisDataCHull*) syncState->analysisData;
242
243 for (i= 0; i < syncState->traceNb; i++)
244 {
245 for (j= 0; j < syncState->traceNb; j++)
246 {
247 if (i != j)
248 {
249 g_queue_foreach(analysisData->hullArray[i][j],
250 &gfDumpHullToFile,
251 analysisData->graphsData->hullPoints[i][j]);
252 }
253 }
254 }
255 }
256
257
258 /*
259 * A GFunc for g_queue_foreach. Write a hull point to a file used to generate
260 * graphs
261 *
262 * Args:
263 * data: Point*, point to write to the file
264 * userData: FILE*, file pointer where to write the point
265 */
266 static void gfDumpHullToFile(gpointer data, gpointer userData)
267 {
268 Point* point;
269
270 point= (Point*) data;
271 fprintf((FILE*) userData, "%20llu %20llu\n", point->x, point->y);
272 }
273
274
275 /*
276 * Close files used to store convex hull points to generate graphs.
277 * Deallocate array to store file pointers.
278 *
279 * Args:
280 * syncState: container for synchronization data
281 */
282 static void closeGraphFiles(SyncState* const syncState)
283 {
284 unsigned int i, j;
285 AnalysisDataCHull* analysisData;
286 int retval;
287
288 analysisData= (AnalysisDataCHull*) syncState->analysisData;
289
290 if (analysisData->graphsData->hullPoints == NULL)
291 {
292 return;
293 }
294
295 for (i= 0; i < syncState->traceNb; i++)
296 {
297 for (j= 0; j < syncState->traceNb; j++)
298 {
299 if (i != j)
300 {
301 retval= fclose(analysisData->graphsData->hullPoints[i][j]);
302 if (retval != 0)
303 {
304 g_error(strerror(errno));
305 }
306 }
307 }
308 free(analysisData->graphsData->hullPoints[i]);
309 }
310 free(analysisData->graphsData->hullPoints);
311 analysisData->graphsData->hullPoints= NULL;
312 }
313
314
315 /*
316 * Analysis destroy function
317 *
318 * Free the analysis specific data structures
319 *
320 * Args:
321 * syncState container for synchronization data.
322 * This function deallocates these analysisData members:
323 * hullArray
324 * stDev
325 */
326 static void destroyAnalysisCHull(SyncState* const syncState)
327 {
328 unsigned int i, j;
329 AnalysisDataCHull* analysisData;
330
331 analysisData= (AnalysisDataCHull*) syncState->analysisData;
332
333 if (analysisData == NULL)
334 {
335 return;
336 }
337
338 for (i= 0; i < syncState->traceNb; i++)
339 {
340 for (j= 0; j < syncState->traceNb; j++)
341 {
342 g_queue_foreach(analysisData->hullArray[i][j], gfPointDestroy, NULL);
343 }
344 free(analysisData->hullArray[i]);
345 }
346 free(analysisData->hullArray);
347
348 if (syncState->stats)
349 {
350 if (analysisData->stats->allFactors != NULL)
351 {
352 freeAllFactors(syncState, analysisData->stats->allFactors);
353 }
354
355 free(analysisData->stats);
356 }
357
358 if (syncState->graphs)
359 {
360 if (analysisData->graphsData->hullPoints != NULL)
361 {
362 closeGraphFiles(syncState);
363 }
364
365 if (!syncState->stats && analysisData->graphsData->allFactors != NULL)
366 {
367 freeAllFactors(syncState, analysisData->graphsData->allFactors);
368 }
369
370 free(analysisData->graphsData);
371 }
372
373 free(syncState->analysisData);
374 syncState->analysisData= NULL;
375 }
376
377
378 /*
379 * Perform analysis on an event pair.
380 *
381 * Args:
382 * syncState container for synchronization data
383 * packet structure containing the events
384 */
385 static void analyzePacketCHull(SyncState* const syncState, Packet* const packet)
386 {
387 AnalysisDataCHull* analysisData;
388 Point* newPoint;
389 HullType hullType;
390 GQueue* hull;
391
392 analysisData= (AnalysisDataCHull*) syncState->analysisData;
393
394 newPoint= malloc(sizeof(Point));
395 if (packet->inE->traceNum < packet->outE->traceNum)
396 {
397 // CA is inE->traceNum
398 newPoint->x= packet->inE->tsc;
399 newPoint->y= packet->outE->tsc;
400 hullType= UPPER;
401 g_debug("Reception point hullArray[%lu][%lu] x= inE->tsc= %llu y= outE->tsc= %llu",
402 packet->inE->traceNum, packet->outE->traceNum, newPoint->x,
403 newPoint->y);
404 }
405 else
406 {
407 // CA is outE->traceNum
408 newPoint->x= packet->outE->tsc;
409 newPoint->y= packet->inE->tsc;
410 hullType= LOWER;
411 g_debug("Send point hullArray[%lu][%lu] x= inE->tsc= %llu y= outE->tsc= %llu",
412 packet->inE->traceNum, packet->outE->traceNum, newPoint->x,
413 newPoint->y);
414 }
415
416 hull=
417 analysisData->hullArray[packet->inE->traceNum][packet->outE->traceNum];
418
419 if (hull->length >= 1 && newPoint->x < ((Point*)
420 g_queue_peek_tail(hull))->x)
421 {
422 if (syncState->stats)
423 {
424 analysisData->stats->dropped++;
425 }
426
427 free(newPoint);
428 }
429 else
430 {
431 grahamScan(hull, newPoint, hullType);
432 }
433 }
434
435
436 /*
437 * Construct one half of a convex hull from abscissa-sorted points
438 *
439 * Args:
440 * hull: the points already in the hull
441 * newPoint: a new point to consider
442 * type: which half of the hull to construct
443 */
444 static void grahamScan(GQueue* const hull, Point* const newPoint, const
445 HullType type)
446 {
447 int inversionFactor;
448
449 g_debug("grahamScan(hull (length: %u), newPoint, %s)", hull->length, type
450 == LOWER ? "LOWER" : "UPPER");
451
452 if (type == LOWER)
453 {
454 inversionFactor= 1;
455 }
456 else
457 {
458 inversionFactor= -1;
459 }
460
461 if (hull->length >= 2)
462 {
463 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
464 hull->length - 2,
465 hull->length - 1,
466 jointCmp(g_queue_peek_nth(hull, hull->length - 2),
467 g_queue_peek_tail(hull), newPoint),
468 inversionFactor,
469 jointCmp(g_queue_peek_nth(hull, hull->length - 2),
470 g_queue_peek_tail(hull), newPoint) * inversionFactor);
471 }
472 while (hull->length >= 2 && jointCmp(g_queue_peek_nth(hull, hull->length -
473 2), g_queue_peek_tail(hull), newPoint) * inversionFactor <= 0)
474 {
475 g_debug("Removing hull[%u]", hull->length);
476 free((Point*) g_queue_pop_tail(hull));
477
478 if (hull->length >= 2)
479 {
480 g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d",
481 hull->length - 2,
482 hull->length - 1,
483 jointCmp(g_queue_peek_nth(hull, hull->length - 2),
484 g_queue_peek_tail(hull), newPoint),
485 inversionFactor,
486 jointCmp(g_queue_peek_nth(hull, hull->length - 2),
487 g_queue_peek_tail(hull), newPoint) * inversionFactor);
488 }
489 }
490 g_queue_push_tail(hull, newPoint);
491 }
492
493
494 /*
495 * Finalize the factor calculations
496 *
497 * Args:
498 * syncState container for synchronization data.
499 *
500 * Returns:
501 * Factors[traceNb] synchronization factors for each trace
502 */
503 static GArray* finalizeAnalysisCHull(SyncState* const syncState)
504 {
505 AnalysisDataCHull* analysisData;
506 GArray* factors;
507 FactorsCHull** allFactors;
508
509 analysisData= (AnalysisDataCHull*) syncState->analysisData;
510
511 if (syncState->graphs)
512 {
513 writeGraphFiles(syncState);
514 closeGraphFiles(syncState);
515 }
516
517 allFactors= calculateAllFactors(syncState);
518
519 factors= reduceFactors(syncState, allFactors);
520
521 if (syncState->stats || syncState->graphs)
522 {
523 if (syncState->stats)
524 {
525 analysisData->stats->allFactors= allFactors;
526 }
527
528 if (syncState->graphs)
529 {
530 analysisData->graphsData->allFactors= allFactors;
531 }
532 }
533 else
534 {
535 freeAllFactors(syncState, allFactors);
536 }
537
538 return factors;
539 }
540
541
542 /*
543 * Print statistics related to analysis. Must be called after
544 * finalizeAnalysis.
545 *
546 * Args:
547 * syncState container for synchronization data.
548 */
549 static void printAnalysisStatsCHull(SyncState* const syncState)
550 {
551 AnalysisDataCHull* analysisData;
552 unsigned int i, j;
553
554 if (!syncState->stats)
555 {
556 return;
557 }
558
559 analysisData= (AnalysisDataCHull*) syncState->analysisData;
560
561 printf("Convex hull analysis stats:\n");
562 printf("\tout of order packets dropped from analysis: %u\n",
563 analysisData->stats->dropped);
564
565 printf("\tNumber of points in convex hulls:\n");
566
567 for (i= 0; i < syncState->traceNb; i++)
568 {
569 for (j= i + 1; j < syncState->traceNb; j++)
570 {
571 printf("\t\t%3d - %-3d: lower half-hull %-5u upper half-hull %-5u\n",
572 i, j, analysisData->hullArray[j][i]->length,
573 analysisData->hullArray[i][j]->length);
574 }
575 }
576
577 printf("\tIndividual synchronization factors:\n");
578
579 for (i= 0; i < syncState->traceNb; i++)
580 {
581 for (j= i + 1; j < syncState->traceNb; j++)
582 {
583 FactorsCHull* factorsCHull;
584
585 factorsCHull= &analysisData->stats->allFactors[j][i];
586 printf("\t\t%3d - %-3d: ", i, j);
587
588 if (factorsCHull->type == EXACT)
589 {
590 printf("Exact a0= % 7g a1= 1 %c %7g\n",
591 factorsCHull->approx->offset,
592 factorsCHull->approx->drift < 0. ? '-' : '+',
593 fabs(factorsCHull->approx->drift));
594 }
595 else if (factorsCHull->type == MIDDLE)
596 {
597 printf("Middle a0= % 7g a1= 1 %c %7g accuracy %7g\n",
598 factorsCHull->approx->offset, factorsCHull->approx->drift
599 - 1. < 0. ? '-' : '+', fabs(factorsCHull->approx->drift -
600 1.), factorsCHull->accuracy);
601 printf("\t\t a0: % 7g to % 7g (delta= %7g)\n",
602 factorsCHull->max->offset, factorsCHull->min->offset,
603 factorsCHull->min->offset - factorsCHull->max->offset);
604 printf("\t\t a1: 1 %+7g to %+7g (delta= %7g)\n",
605 factorsCHull->min->drift - 1., factorsCHull->max->drift -
606 1., factorsCHull->max->drift - factorsCHull->min->drift);
607 }
608 else if (factorsCHull->type == FALLBACK)
609 {
610 printf("Fallback a0= % 7g a1= 1 %c %7g error= %7g\n",
611 factorsCHull->approx->offset, factorsCHull->approx->drift
612 - 1. < 0. ? '-' : '+', fabs(factorsCHull->approx->drift -
613 1.), factorsCHull->accuracy);
614 }
615 else if (factorsCHull->type == INCOMPLETE)
616 {
617 printf("Incomplete\n");
618
619 if (factorsCHull->min->drift != -INFINITY)
620 {
621 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
622 factorsCHull->min->offset, factorsCHull->min->drift -
623 1. < 0 ? '-' : '+', fabs(factorsCHull->min->drift -
624 1.));
625 }
626 if (factorsCHull->max->drift != INFINITY)
627 {
628 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
629 factorsCHull->max->offset, factorsCHull->max->drift -
630 1. < 0 ? '-' : '+', fabs(factorsCHull->max->drift -
631 1.));
632 }
633 }
634 else if (factorsCHull->type == SCREWED)
635 {
636 printf("Screwed\n");
637
638 if (factorsCHull->min != NULL && factorsCHull->min->drift != -INFINITY)
639 {
640 printf("\t\t min: a0: % 7g a1: 1 %c %7g\n",
641 factorsCHull->min->offset, factorsCHull->min->drift -
642 1. < 0 ? '-' : '+', fabs(factorsCHull->min->drift -
643 1.));
644 }
645 if (factorsCHull->max != NULL && factorsCHull->max->drift != INFINITY)
646 {
647 printf("\t\t max: a0: % 7g a1: 1 %c %7g\n",
648 factorsCHull->max->offset, factorsCHull->max->drift -
649 1. < 0 ? '-' : '+', fabs(factorsCHull->max->drift -
650 1.));
651 }
652 }
653 else if (factorsCHull->type == ABSENT)
654 {
655 printf("Absent\n");
656 }
657 else
658 {
659 g_assert_not_reached();
660 }
661 }
662 }
663 }
664
665
666 /*
667 * A GFunc for g_queue_foreach()
668 *
669 * Args:
670 * data Point*, point to destroy
671 * user_data NULL
672 */
673 static void gfPointDestroy(gpointer data, gpointer userData)
674 {
675 Point* point;
676
677 point= (Point*) data;
678 free(point);
679 }
680
681
682 /*
683 * Find out if a sequence of three points constitutes a "left turn" or a
684 * "right turn".
685 *
686 * Args:
687 * p1, p2, p3: The three points.
688 *
689 * Returns:
690 * < 0 right turn
691 * 0 colinear (unlikely result since this uses floating point
692 * arithmetic)
693 * > 0 left turn
694 */
695 static int jointCmp(const Point const* p1, const Point const* p2, const
696 Point const* p3)
697 {
698 double result;
699 const double fuzzFactor= 0.;
700
701 result= crossProductK(p1, p2, p1, p3);
702 g_debug("crossProductK(p1= (%llu, %llu), p2= (%llu, %llu), p1= (%llu, %llu), p3= (%llu, %llu))= %g",
703 p1->x, p1->y, p2->x, p2->y, p1->x, p1->y, p3->x, p3->y, result);
704 if (result < fuzzFactor)
705 {
706 return -1;
707 }
708 else if (result > fuzzFactor)
709 {
710 return 1;
711 }
712 else
713 {
714 return 0;
715 }
716 }
717
718
719 /*
720 * Calculate the k component of the cross product of two vectors.
721 *
722 * Args:
723 * p1, p2: start and end points of the first vector
724 * p3, p4: start and end points of the second vector
725 *
726 * Returns:
727 * the k component of the cross product when considering the two vectors to
728 * be in the i-j plane. The direction (sign) of the result can be useful to
729 * determine the relative orientation of the two vectors.
730 */
731 static double crossProductK(const Point const* p1, const Point const* p2,
732 const Point const* p3, const Point const* p4)
733 {
734 return ((double) p2->x - p1->x) * ((double) p4->y - p3->y) - ((double)
735 p2->y - p1->y) * ((double) p4->x - p3->x);
736 }
737
738
739 /*
740 * Free a container of FactorsCHull
741 *
742 * Args:
743 * syncState: container for synchronization data.
744 * allFactors: container of Factors
745 */
746 static void freeAllFactors(const SyncState* const syncState, FactorsCHull**
747 const allFactors)
748 {
749 unsigned int i, j;
750
751 for (i= 0; i < syncState->traceNb; i++)
752 {
753 for (j= 0; j <= i; j++)
754 {
755 FactorsCHull* factorsCHull;
756
757 factorsCHull= &allFactors[i][j];
758 if (factorsCHull->type == MIDDLE || factorsCHull->type ==
759 INCOMPLETE || factorsCHull->type == ABSENT)
760 {
761 free(factorsCHull->min);
762 free(factorsCHull->max);
763 }
764 else if (factorsCHull->type == SCREWED)
765 {
766 if (factorsCHull->min != NULL)
767 {
768 free(factorsCHull->min);
769 }
770 if (factorsCHull->max != NULL)
771 {
772 free(factorsCHull->max);
773 }
774 }
775
776 if (factorsCHull->type == EXACT || factorsCHull->type == MIDDLE ||
777 factorsCHull->type == FALLBACK)
778 {
779 free(factorsCHull->approx);
780 }
781 }
782 free(allFactors[i]);
783 }
784 free(allFactors);
785 }
786
787
788 /*
789 * Analyze the convex hulls to determine the synchronization factors between
790 * each pair of trace.
791 *
792 * Args:
793 * syncState container for synchronization data.
794 *
795 * Returns:
796 * FactorsCHull*[TraceNum][TraceNum] array. See the documentation for the
797 * member allFactors of AnalysisStatsCHull.
798 */
799 static FactorsCHull** calculateAllFactors(SyncState* const syncState)
800 {
801 unsigned int traceNumA, traceNumB;
802 FactorsCHull** allFactors;
803 AnalysisDataCHull* analysisData;
804
805 analysisData= (AnalysisDataCHull*) syncState->analysisData;
806
807 // Allocate allFactors and calculate min and max
808 allFactors= malloc(syncState->traceNb * sizeof(FactorsCHull*));
809 for (traceNumA= 0; traceNumA < syncState->traceNb; traceNumA++)
810 {
811 allFactors[traceNumA]= malloc((traceNumA + 1) * sizeof(FactorsCHull));
812
813 allFactors[traceNumA][traceNumA].type= EXACT;
814 allFactors[traceNumA][traceNumA].approx= malloc(sizeof(Factors));
815 allFactors[traceNumA][traceNumA].approx->drift= 1.;
816 allFactors[traceNumA][traceNumA].approx->offset= 0.;
817
818 for (traceNumB= 0; traceNumB < traceNumA; traceNumB++)
819 {
820 unsigned int i;
821 GQueue* cs, * cr;
822 const struct
823 {
824 LineType lineType;
825 size_t factorsOffset;
826 } loopValues[]= {
827 {MINIMUM, offsetof(FactorsCHull, min)},
828 {MAXIMUM, offsetof(FactorsCHull, max)}
829 };
830
831 cr= analysisData->hullArray[traceNumB][traceNumA];
832 cs= analysisData->hullArray[traceNumA][traceNumB];
833
834 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
835 {
836 g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= hullArray[%u][%u], cs= hullArray[%u][%u], %s)",
837 traceNumA, traceNumB, loopValues[i].factorsOffset ==
838 offsetof(FactorsCHull, min) ? "min" : "max", traceNumB,
839 traceNumA, traceNumA, traceNumB, loopValues[i].lineType ==
840 MINIMUM ? "MINIMUM" : "MAXIMUM");
841 *((Factors**) ((void*) &allFactors[traceNumA][traceNumB] +
842 loopValues[i].factorsOffset))=
843 calculateFactorsExact(cr, cs, loopValues[i].lineType);
844 }
845 }
846 }
847
848 // Calculate approx when possible
849 for (traceNumA= 0; traceNumA < syncState->traceNb; traceNumA++)
850 {
851 for (traceNumB= 0; traceNumB < traceNumA; traceNumB++)
852 {
853 FactorsCHull* factorsCHull;
854
855 factorsCHull= &allFactors[traceNumA][traceNumB];
856 if (factorsCHull->min == NULL && factorsCHull->max == NULL)
857 {
858 factorsCHull->type= FALLBACK;
859 calculateFactorsFallback(analysisData->hullArray[traceNumB][traceNumA],
860 analysisData->hullArray[traceNumA][traceNumB],
861 &allFactors[traceNumA][traceNumB]);
862 }
863 else if (factorsCHull->min != NULL && factorsCHull->max != NULL)
864 {
865 if (factorsCHull->min->drift != -INFINITY &&
866 factorsCHull->max->drift != INFINITY)
867 {
868 factorsCHull->type= MIDDLE;
869 calculateFactorsMiddle(factorsCHull);
870 }
871 else if (factorsCHull->min->drift != -INFINITY ||
872 factorsCHull->max->drift != INFINITY)
873 {
874 factorsCHull->type= INCOMPLETE;
875 }
876 else
877 {
878 factorsCHull->type= ABSENT;
879 }
880 }
881 else
882 {
883 //g_assert_not_reached();
884 factorsCHull->type= SCREWED;
885 }
886 }
887 }
888
889 return allFactors;
890 }
891
892
893 /* Calculate approximative factors based on minimum and maximum limits. The
894 * best approximation to make is the interior bissector of the angle formed by
895 * the minimum and maximum lines.
896 *
897 * The formulae used come from [Haddad, Yoram: Performance dans les systèmes
898 * répartis: des outils pour les mesures, Université de Paris-Sud, Centre
899 * d'Orsay, September 1988] Section 6.1 p.44
900 *
901 * The reasoning for choosing this estimator comes from [Duda, A., Harrus, G.,
902 * Haddad, Y., and Bernard, G.: Estimating global time in distributed systems,
903 * Proc. 7th Int. Conf. on Distributed Computing Systems, Berlin, volume 18,
904 * 1987] p.303
905 *
906 * Args:
907 * factors: contains the min and max limits, used to store the result
908 */
909 static void calculateFactorsMiddle(FactorsCHull* factors)
910 {
911 double amin, amax, bmin, bmax, bhat;
912
913 amin= factors->max->offset;
914 amax= factors->min->offset;
915 bmin= factors->min->drift;
916 bmax= factors->max->drift;
917
918 g_assert_cmpfloat(bmax, >, bmin);
919
920 factors->approx= malloc(sizeof(Factors));
921 bhat= (bmax * bmin - 1. + sqrt(1. + pow(bmax, 2.) * pow(bmin, 2.) +
922 pow(bmax, 2.) + pow(bmin, 2.))) / (bmax + bmin);
923 factors->approx->offset= amax - (amax - amin) / 2. * (pow(bhat, 2.) + 1.)
924 / (1. + bhat * bmax);
925 factors->approx->drift= bhat;
926 factors->accuracy= bmax - bmin;
927 }
928
929
930 /*
931 * Analyze the convex hulls to determine the minimum or maximum
932 * synchronization factors between one pair of trace.
933 *
934 * This implements and improves upon the algorithm in [Haddad, Yoram:
935 * Performance dans les systèmes répartis: des outils pour les mesures,
936 * Université de Paris-Sud, Centre d'Orsay, September 1988] Section 6.2 p.47
937 *
938 * Some degenerate cases are possible:
939 * 1) the result is unbounded. In that case, when searching for the maximum
940 * factors, result->drift= INFINITY; result->offset= -INFINITY. When
941 * searching for the minimum factors, it is the opposite. It is not
942 * possible to improve the situation with this data.
943 * 2) no line can be above the upper hull and below the lower hull. This is
944 * because the hulls intersect each other or are reversed. This means that
945 * an assertion was false. Most probably, the clocks are not linear. It is
946 * possible to repeat the search with another algorithm that will find a
947 * "best effort" approximation. See calculateFactorsApprox().
948 *
949 * Args:
950 * cu: the upper half-convex hull, the line must pass above this
951 * and touch it in one point
952 * cl: the lower half-convex hull, the line must pass below this
953 * and touch it in one point
954 * lineType: search for minimum or maximum factors
955 *
956 * Returns:
957 * If a result is found, a struct Factors is allocated, filed with the
958 * result and returned
959 * NULL otherwise, degenerate case 2 is in effect
960 */
961 static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const
962 LineType lineType)
963 {
964 GQueue* c1, * c2;
965 unsigned int i1, i2;
966 Point* p1, * p2;
967 double inversionFactor;
968 Factors* result;
969
970 g_debug("calculateFactorsExact(cu= %p, cl= %p, %s)", cu, cl, lineType ==
971 MINIMUM ? "MINIMUM" : "MAXIMUM");
972
973 if (lineType == MINIMUM)
974 {
975 c1= cl;
976 c2= cu;
977 inversionFactor= -1.;
978 }
979 else
980 {
981 c1= cu;
982 c2= cl;
983 inversionFactor= 1.;
984 }
985
986 i1= 0;
987 i2= c2->length - 1;
988
989 // Check for degenerate case 1
990 if (c1->length == 0 || c2->length == 0 || ((Point*) g_queue_peek_nth(c1,
991 i1))->x >= ((Point*) g_queue_peek_nth(c2, i2))->x)
992 {
993 result= malloc(sizeof(Factors));
994 if (lineType == MINIMUM)
995 {
996 result->drift= -INFINITY;
997 result->offset= INFINITY;
998 }
999 else
1000 {
1001 result->drift= INFINITY;
1002 result->offset= -INFINITY;
1003 }
1004
1005 return result;
1006 }
1007
1008 do
1009 {
1010 while
1011 (
1012 (int) i2 - 1 > 0
1013 && crossProductK(
1014 g_queue_peek_nth(c1, i1),
1015 g_queue_peek_nth(c2, i2),
1016 g_queue_peek_nth(c1, i1),
1017 g_queue_peek_nth(c2, i2 - 1)) * inversionFactor < 0.
1018 )
1019 {
1020 if (((Point*) g_queue_peek_nth(c1, i1))->x
1021 < ((Point*) g_queue_peek_nth(c2, i2 - 1))->x)
1022 {
1023 i2--;
1024 }
1025 else
1026 {
1027 // Degenerate case 2
1028 return NULL;
1029 }
1030 }
1031 while
1032 (
1033 i1 + 1 < c1->length - 1
1034 && crossProductK(
1035 g_queue_peek_nth(c1, i1),
1036 g_queue_peek_nth(c2, i2),
1037 g_queue_peek_nth(c1, i1 + 1),
1038 g_queue_peek_nth(c2, i2)) * inversionFactor < 0.
1039 )
1040 {
1041 if (((Point*) g_queue_peek_nth(c1, i1 + 1))->x
1042 < ((Point*) g_queue_peek_nth(c2, i2))->x)
1043 {
1044 i1++;
1045 }
1046 else
1047 {
1048 // Degenerate case 2
1049 return NULL;
1050 }
1051 }
1052 } while
1053 (
1054 (int) i2 - 1 > 0
1055 && crossProductK(
1056 g_queue_peek_nth(c1, i1),
1057 g_queue_peek_nth(c2, i2),
1058 g_queue_peek_nth(c1, i1),
1059 g_queue_peek_nth(c2, i2 - 1)) * inversionFactor < 0.
1060 );
1061
1062 p1= g_queue_peek_nth(c1, i1);
1063 p2= g_queue_peek_nth(c2, i2);
1064
1065 g_debug("Resulting points are: c1[i1]: x= %llu y= %llu c2[i2]: x= %llu y= %llu",
1066 p1->x, p1->y, p2->x, p2->y);
1067
1068 result= malloc(sizeof(Factors));
1069 result->drift= slope(p1, p2);
1070 result->offset= intercept(p1, p2);
1071
1072 g_debug("Resulting factors are: drift= %g offset= %g", result->drift, result->offset);
1073
1074 return result;
1075 }
1076
1077
1078 /*
1079 * Analyze the convex hulls to determine approximate synchronization factors
1080 * between one pair of trace when there is no line that can fit in the
1081 * corridor separating them.
1082 *
1083 * This implements the algorithm in [Ashton, P.: Algorithms for Off-line Clock
1084 * Synchronisation, University of Canterbury, December 1995, 26] Section 4.2.2
1085 * p.7
1086 *
1087 * For each point p1 in cr
1088 * For each point p2 in cs
1089 * errorMin= 0
1090 * Calculate the line paramaters
1091 * For each point p3 in each convex hull
1092 * If p3 is on the wrong side of the line
1093 * error+= distance
1094 * If error < errorMin
1095 * Update results
1096 *
1097 * Args:
1098 * cr: the upper half-convex hull
1099 * cs: the lower half-convex hull
1100 * result: a pointer to the pre-allocated struct where the results
1101 * will be stored
1102 */
1103 static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs,
1104 FactorsCHull* const result)
1105 {
1106 unsigned int i, j, k;
1107 double errorMin;
1108 Factors* approx;
1109
1110 errorMin= INFINITY;
1111 approx= malloc(sizeof(Factors));
1112
1113 for (i= 0; i < cs->length; i++)
1114 {
1115 for (j= 0; j < cr->length; j++)
1116 {
1117 double error;
1118 Point p1, p2;
1119
1120 error= 0.;
1121
1122 if (((Point*) g_queue_peek_nth(cs, i))->x < ((Point*)g_queue_peek_nth(cr, j))->x)
1123 {
1124 p1= *(Point*)g_queue_peek_nth(cs, i);
1125 p2= *(Point*)g_queue_peek_nth(cr, j);
1126 }
1127 else
1128 {
1129 p1= *(Point*)g_queue_peek_nth(cr, j);
1130 p2= *(Point*)g_queue_peek_nth(cs, i);
1131 }
1132
1133 // The lower hull should be above the point
1134 for (k= 0; k < cs->length; k++)
1135 {
1136 if (jointCmp(&p1, &p2, g_queue_peek_nth(cs, k)) < 0.)
1137 {
1138 error+= verticalDistance(&p1, &p2, g_queue_peek_nth(cs, k));
1139 }
1140 }
1141
1142 // The upper hull should be below the point
1143 for (k= 0; k < cr->length; k++)
1144 {
1145 if (jointCmp(&p1, &p2, g_queue_peek_nth(cr, k)) > 0.)
1146 {
1147 error+= verticalDistance(&p1, &p2, g_queue_peek_nth(cr, k));
1148 }
1149 }
1150
1151 if (error < errorMin)
1152 {
1153 g_debug("Fallback: i= %u j= %u is a better match (error= %g)", i, j, error);
1154 approx->drift= slope(&p1, &p2);
1155 approx->offset= intercept(&p1, &p2);
1156 errorMin= error;
1157 }
1158 }
1159 }
1160
1161 result->approx= approx;
1162 result->accuracy= errorMin;
1163 }
1164
1165
1166 /*
1167 * Calculate the vertical distance between a line and a point
1168 *
1169 * Args:
1170 * p1, p2: Two points defining the line
1171 * point: a point
1172 *
1173 * Return:
1174 * the vertical distance
1175 */
1176 static double verticalDistance(Point* p1, Point* p2, Point* const point)
1177 {
1178 return fabs(slope(p1, p2) * point->x + intercept(p1, p2) - point->y);
1179 }
1180
1181
1182 /*
1183 * Calculate the slope between two points
1184 *
1185 * Args:
1186 * p1, p2 the two points
1187 *
1188 * Returns:
1189 * the slope
1190 */
1191 static double slope(const Point* const p1, const Point* const p2)
1192 {
1193 return ((double) p2->y - p1->y) / (p2->x - p1->x);
1194 }
1195
1196
1197 /* Calculate the y-intercept of a line that passes by two points
1198 *
1199 * Args:
1200 * p1, p2 the two points
1201 *
1202 * Returns:
1203 * the y-intercept
1204 */
1205 static double intercept(const Point* const p1, const Point* const p2)
1206 {
1207 return ((double) p2->y * p1->x - (double) p1->y * p2->x) / ((double) p1->x - p2->x);
1208 }
1209
1210
1211 /*
1212 * Calculate a resulting offset and drift for each trace.
1213 *
1214 * Traces are assembled in groups. A group is an "island" of nodes/traces that
1215 * exchanged messages. A reference is determined for each group by using a
1216 * shortest path search based on the accuracy of the approximation. This also
1217 * forms a tree of the best way to relate each node's clock to the reference's
1218 * based on the accuracy. Sometimes it may be necessary or advantageous to
1219 * propagate the factors through intermediary clocks. Resulting factors for
1220 * each trace are determined based on this tree.
1221 *
1222 * This part was not the focus of my research. The algorithm used here is
1223 * inexact in some ways:
1224 * 1) The reference used may not actually be the best one to use. This is
1225 * because the accuracy is not corrected based on the drift during the
1226 * shortest path search.
1227 * 2) The min and max factors are not propagated and are no longer valid.
1228 * 3) Approximations of different types (MIDDLE and FALLBACK) are compared
1229 * together. The "accuracy" parameters of these have different meanings and
1230 * are not readily comparable.
1231 *
1232 * Nevertheless, the result is satisfactory. You just can't tell "how much" it
1233 * is.
1234 *
1235 * Two alternative (and subtly different) ways of propagating factors to
1236 * preserve min and max bondaries have been proposed, see:
1237 * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time
1238 * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing
1239 * Systems, Berlin, volume 18, 1987] p.304
1240 *
1241 * [Jezequel, J.M., and Jard, C.: Building a global clock for observing
1242 * computations in distributed memory parallel computers, Concurrency:
1243 * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester,
1244 * 1996, 32] Section 5; which is mostly the same as
1245 * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings
1246 * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume
1247 * 392, 136–147, 1989] Section 5
1248 *
1249 * Args:
1250 * syncState: container for synchronization data.
1251 * allFactors: offset and drift between each pair of traces
1252 *
1253 * Returns:
1254 * Factors[traceNb] synchronization factors for each trace
1255 */
1256 static GArray* reduceFactors(SyncState* const syncState, FactorsCHull** const
1257 allFactors)
1258 {
1259 GArray* factors;
1260 double** distances;
1261 unsigned int** predecessors;
1262 double* distanceSums;
1263 unsigned int* references;
1264 unsigned int i, j;
1265
1266 // Solve the all-pairs shortest path problem using the Floyd-Warshall
1267 // algorithm
1268 floydWarshall(syncState, allFactors, &distances, &predecessors);
1269
1270 /* Find the reference for each node
1271 *
1272 * First calculate, for each node, the sum of the distances to each other
1273 * node it can reach.
1274 *
1275 * Then, go through each "island" of traces to find the trace that has the
1276 * lowest distance sum. Assign this trace as the reference to each trace
1277 * of the island.
1278 */
1279 distanceSums= malloc(syncState->traceNb * sizeof(double));
1280 for (i= 0; i < syncState->traceNb; i++)
1281 {
1282 distanceSums[i]= 0.;
1283 for (j= 0; j < syncState->traceNb; j++)
1284 {
1285 distanceSums[i]+= distances[i][j];
1286 }
1287 }
1288
1289 references= malloc(syncState->traceNb * sizeof(unsigned int));
1290 for (i= 0; i < syncState->traceNb; i++)
1291 {
1292 references[i]= UINT_MAX;
1293 }
1294 for (i= 0; i < syncState->traceNb; i++)
1295 {
1296 if (references[i] == UINT_MAX)
1297 {
1298 unsigned int reference;
1299 double distanceSumMin;
1300
1301 // A node is its own reference by default
1302 reference= i;
1303 distanceSumMin= INFINITY;
1304 for (j= 0; j < syncState->traceNb; j++)
1305 {
1306 if (distances[i][j] != INFINITY && distanceSums[j] <
1307 distanceSumMin)
1308 {
1309 reference= j;
1310 distanceSumMin= distanceSums[j];
1311 }
1312 }
1313 for (j= 0; j < syncState->traceNb; j++)
1314 {
1315 if (distances[i][j] != INFINITY)
1316 {
1317 references[j]= reference;
1318 }
1319 }
1320 }
1321 }
1322
1323 for (i= 0; i < syncState->traceNb; i++)
1324 {
1325 free(distances[i]);
1326 }
1327 free(distances);
1328 free(distanceSums);
1329
1330 /* For each trace, calculate the factors based on their corresponding
1331 * tree. The tree is rooted at the reference and the shortest path to each
1332 * other nodes are the branches.
1333 */
1334 factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
1335 syncState->traceNb);
1336 g_array_set_size(factors, syncState->traceNb);
1337 for (i= 0; i < syncState->traceNb; i++)
1338 {
1339 getFactors(allFactors, predecessors, references, i, &g_array_index(factors,
1340 Factors, i));
1341 }
1342
1343 for (i= 0; i < syncState->traceNb; i++)
1344 {
1345 free(predecessors[i]);
1346 }
1347 free(predecessors);
1348 free(references);
1349
1350 return factors;
1351 }
1352
1353
1354 /*
1355 * Perform an all-source shortest path search using the Floyd-Warshall
1356 * algorithm.
1357 *
1358 * The algorithm is implemented accoding to the description here:
1359 * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
1360 *
1361 * Args:
1362 * syncState: container for synchronization data.
1363 * allFactors: offset and drift between each pair of traces
1364 * distances: resulting matrix of the length of the shortest path between
1365 * two nodes. If there is no path between two nodes, the
1366 * length is INFINITY
1367 * predecessors: resulting matrix of each node's predecessor on the shortest
1368 * path between two nodes
1369 */
1370 static void floydWarshall(SyncState* const syncState, FactorsCHull** const
1371 allFactors, double*** const distances, unsigned int*** const
1372 predecessors)
1373 {
1374 unsigned int i, j, k;
1375
1376 // Setup initial conditions
1377 *distances= malloc(syncState->traceNb * sizeof(double*));
1378 *predecessors= malloc(syncState->traceNb * sizeof(unsigned int*));
1379 for (i= 0; i < syncState->traceNb; i++)
1380 {
1381 (*distances)[i]= malloc(syncState->traceNb * sizeof(double));
1382 for (j= 0; j < syncState->traceNb; j++)
1383 {
1384 if (i == j)
1385 {
1386 g_assert(allFactors[i][j].type == EXACT);
1387
1388 (*distances)[i][j]= 0.;
1389 }
1390 else
1391 {
1392 unsigned int row, col;
1393
1394 if (i > j)
1395 {
1396 row= i;
1397 col= j;
1398 }
1399 else if (i < j)
1400 {
1401 row= j;
1402 col= i;
1403 }
1404
1405 if (allFactors[row][col].type == MIDDLE ||
1406 allFactors[row][col].type == FALLBACK)
1407 {
1408 (*distances)[i][j]= allFactors[row][col].accuracy;
1409 }
1410 else if (allFactors[row][col].type == INCOMPLETE ||
1411 allFactors[row][col].type == SCREWED ||
1412 allFactors[row][col].type == ABSENT)
1413 {
1414 (*distances)[i][j]= INFINITY;
1415 }
1416 else
1417 {
1418 g_assert_not_reached();
1419 }
1420 }
1421 }
1422
1423 (*predecessors)[i]= malloc(syncState->traceNb * sizeof(unsigned int));
1424 for (j= 0; j < syncState->traceNb; j++)
1425 {
1426 if (i != j)
1427 {
1428 (*predecessors)[i][j]= i;
1429 }
1430 else
1431 {
1432 (*predecessors)[i][j]= UINT_MAX;
1433 }
1434 }
1435 }
1436
1437 // Run the iterations
1438 for (k= 0; k < syncState->traceNb; k++)
1439 {
1440 for (i= 0; i < syncState->traceNb; i++)
1441 {
1442 for (j= 0; j < syncState->traceNb; j++)
1443 {
1444 double distanceMin;
1445
1446 distanceMin= MIN((*distances)[i][j], (*distances)[i][k] +
1447 (*distances)[k][j]);
1448
1449 if (distanceMin != (*distances)[i][j])
1450 {
1451 (*predecessors)[i][j]= (*predecessors)[k][j];
1452 }
1453
1454 (*distances)[i][j]= distanceMin;
1455 }
1456 }
1457 }
1458 }
1459
1460
1461 /*
1462 * Cummulate the time correction factors to convert a node's time to its
1463 * reference's time.
1464 * This function recursively calls itself until it reaches the reference node.
1465 *
1466 * Args:
1467 * allFactors: offset and drift between each pair of traces
1468 * predecessors: matrix of each node's predecessor on the shortest
1469 * path between two nodes
1470 * references: reference node for each node
1471 * traceNum: node for which to find the factors
1472 * factors: resulting factors
1473 */
1474 static void getFactors(FactorsCHull** const allFactors, unsigned int** const
1475 predecessors, unsigned int* const references, const unsigned int traceNum,
1476 Factors* const factors)
1477 {
1478 unsigned int reference;
1479
1480 reference= references[traceNum];
1481
1482 if (reference == traceNum)
1483 {
1484 factors->offset= 0.;
1485 factors->drift= 1.;
1486 }
1487 else
1488 {
1489 Factors previousVertexFactors;
1490
1491 getFactors(allFactors, predecessors, references,
1492 predecessors[reference][traceNum], &previousVertexFactors);
1493
1494 // convertir de traceNum à reference
1495
1496 // allFactors convertit de col à row
1497
1498 if (reference > traceNum)
1499 {
1500 factors->offset= previousVertexFactors.drift *
1501 allFactors[reference][traceNum].approx->offset +
1502 previousVertexFactors.offset;
1503 factors->drift= previousVertexFactors.drift *
1504 allFactors[reference][traceNum].approx->drift;
1505 }
1506 else
1507 {
1508 factors->offset= previousVertexFactors.drift * (-1. *
1509 allFactors[traceNum][reference].approx->offset /
1510 allFactors[traceNum][reference].approx->drift) +
1511 previousVertexFactors.offset;
1512 factors->drift= previousVertexFactors.drift * (1. /
1513 allFactors[traceNum][reference].approx->drift);
1514 }
1515 }
1516 }
1517
1518
1519 /*
1520 * Write the analysis-specific graph lines in the gnuplot script.
1521 *
1522 * Args:
1523 * stream: stream where to write the data
1524 * syncState: container for synchronization data
1525 * i: first trace number
1526 * j: second trace number, garanteed to be larger than i
1527 */
1528 void writeAnalysisGraphsPlotsCHull(FILE* stream, SyncState* const syncState,
1529 const unsigned int i, const unsigned int j)
1530 {
1531 AnalysisDataCHull* analysisData;
1532 FactorsCHull* factorsCHull;
1533
1534 analysisData= (AnalysisDataCHull*) syncState->analysisData;
1535
1536 fprintf(stream,
1537 "\t\"analysis_chull-%1$03d_to_%2$03d.data\" "
1538 "title \"Lower half-hull\" with linespoints "
1539 "linecolor rgb \"#015a01\" linetype 4 pointtype 8 pointsize 0.8, \\\n"
1540 "\t\"analysis_chull-%2$03d_to_%1$03d.data\" "
1541 "title \"Upper half-hull\" with linespoints "
1542 "linecolor rgb \"#003366\" linetype 4 pointtype 10 pointsize 0.8, \\\n",
1543 i, j);
1544
1545 factorsCHull= &analysisData->graphsData->allFactors[j][i];
1546 if (factorsCHull->type == EXACT)
1547 {
1548 fprintf(stream,
1549 "\t%7g + %7g * x "
1550 "title \"Exact conversion\" with lines "
1551 "linecolor rgb \"black\" linetype 1, \\\n",
1552 factorsCHull->approx->offset, factorsCHull->approx->drift);
1553 }
1554 else if (factorsCHull->type == MIDDLE)
1555 {
1556 fprintf(stream,
1557 "\t%.2f + %.10f * x "
1558 "title \"Min conversion\" with lines "
1559 "linecolor rgb \"black\" linetype 5, \\\n",
1560 factorsCHull->min->offset, factorsCHull->min->drift);
1561 fprintf(stream,
1562 "\t%.2f + %.10f * x "
1563 "title \"Max conversion\" with lines "
1564 "linecolor rgb \"black\" linetype 8, \\\n",
1565 factorsCHull->max->offset, factorsCHull->max->drift);
1566 fprintf(stream,
1567 "\t%.2f + %.10f * x "
1568 "title \"Middle conversion\" with lines "
1569 "linecolor rgb \"gray60\" linetype 1, \\\n",
1570 factorsCHull->approx->offset, factorsCHull->approx->drift);
1571 }
1572 else if (factorsCHull->type == FALLBACK)
1573 {
1574 fprintf(stream,
1575 "\t%.2f + %.10f * x "
1576 "title \"Fallback conversion\" with lines "
1577 "linecolor rgb \"gray60\" linetype 1, \\\n",
1578 factorsCHull->approx->offset, factorsCHull->approx->drift);
1579 }
1580 else if (factorsCHull->type == INCOMPLETE)
1581 {
1582 if (factorsCHull->min->drift != -INFINITY)
1583 {
1584 fprintf(stream,
1585 "\t%.2f + %.10f * x "
1586 "title \"Min conversion\" with lines "
1587 "linecolor rgb \"black\" linetype 5, \\\n",
1588 factorsCHull->min->offset, factorsCHull->min->drift);
1589 }
1590
1591 if (factorsCHull->max->drift != INFINITY)
1592 {
1593 fprintf(stream,
1594 "\t%.2f + %.10f * x "
1595 "title \"Max conversion\" with lines "
1596 "linecolor rgb \"black\" linetype 8, \\\n",
1597 factorsCHull->max->offset, factorsCHull->max->drift);
1598 }
1599 }
1600 else if (factorsCHull->type == SCREWED)
1601 {
1602 if (factorsCHull->min != NULL && factorsCHull->min->drift != -INFINITY)
1603 {
1604 fprintf(stream,
1605 "\t%.2f + %.10f * x "
1606 "title \"Min conversion\" with lines "
1607 "linecolor rgb \"black\" linetype 5, \\\n",
1608 factorsCHull->min->offset, factorsCHull->min->drift);
1609 }
1610
1611 if (factorsCHull->max != NULL && factorsCHull->max->drift != INFINITY)
1612 {
1613 fprintf(stream,
1614 "\t%.2f + %.10f * x "
1615 "title \"Max conversion\" with lines "
1616 "linecolor rgb \"black\" linetype 8, \\\n",
1617 factorsCHull->max->offset, factorsCHull->max->drift);
1618 }
1619 }
1620 else if (factorsCHull->type == ABSENT)
1621 {
1622 }
1623 else
1624 {
1625 g_assert_not_reached();
1626 }
1627 }
LTTng 2.x Viewer (LTTV)
This page took 0.099602 seconds and 4 git commands to generate.