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