lttv/lttv/sync/event_analysis_chull.h

   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
  19 #ifndef EVENT_ANALYSIS_CHULL_H
  20 #define EVENT_ANALYSIS_CHULL_H
  21
  22 #include <glib.h>
  23
  24 #include "data_structures.h"
  25
  26
  27 typedef struct
  28 {
  29         uint64_t x, y;
  30 } Point;
  31
  32
  33 typedef enum
  34 {
  35         EXACT,
  36         /* Used for identity factors (a0= 0, a1= 1) that map a trace to itself. In
  37          * this case, min, max and accuracy are not initialized.
  38          */
  39
  40         MIDDLE,
  41         /* The approximation is the middle of the min and max limits, all fields
  42          * are initialized.
  43          */
  44
  45         FALLBACK,
  46         /* min and max are not available because the hulls do not respect
  47          * assumptions (hulls should not intersect and the upper half-hull should
  48          * be below the lower half-hull). The approximation is a "best effort".
  49          * All fields are initialized but min and max are NULL.
  50          */
  51
  52         INCOMPLETE,
  53         /* min or max is available but not both. The hulls respected assumptions
  54          * but all receives took place after all sends or vice versa. approx and
  55          * accuracy are not initialized.
  56          */
  57
  58         ABSENT,
  59         /* The pair of trace did not have communications in both directions (maybe
  60          * even no communication at all). approx and accuracy are not initialized.
  61          */
  62
  63         SCREWED,
  64         /* min and max are not available because the algorithms are screwed. One
  65          * of min or max (but not both) is NULL. The other is initialized. Approx
  66          * is not initialized.
  67          */
  68
  69         APPROX_NB, // This must be the last member
  70 } ApproxType;
  71
  72 extern const char* const approxNames[APPROX_NB];
  73
  74 typedef struct
  75 {
  76         Factors* min, * max, * approx;
  77         ApproxType type;
  78         double accuracy;
  79 } FactorsCHull;
  80
  81
  82 typedef struct
  83 {
  84         unsigned int dropped;
  85
  86         /* FactorsCHull allFactors[traceNb][traceNb]
  87          *
  88          * allFactors is divided into three parts depending on the position of an
  89          * element allFactors[i][j]:
  90          *   Lower triangular part of the matrix
  91          *     i > j
  92          *     This contains the factors between nodes i and j. These factors
  93          *     convert the time values of j to time values of i.
  94          *   Diagonal part of the matrix
  95          *     i = j
  96          *     This contains identity factors (a0= 0, a1= 1).
  97          *   Upper triangular part of the matrix
  98          *     i < j
  99          *     This area is not allocated.
 100          */
 101         FactorsCHull** allFactors;
 102 } AnalysisStatsCHull;
 103
 104
 105 typedef struct
 106 {
 107         /* This array contains file pointers to files where hull points x-y data
 108          * is outputed. Each trace-pair has two files, one for each message
 109          * direction. The structure of the array is the same as for hullArray,
 110          * hullPoints[row][col] where:
 111          *   row= inE->traceNum
 112          *   col= outE->traceNum
 113          *
 114          * The elements on the diagonal are not initialized.
 115          */
 116         FILE*** hullPoints;
 117
 118         /* FactorsCHull allFactors[traceNb][traceNb]
 119          * This is the same array as AnalysisStatsCHull.allFactors.
 120          */
 121         FactorsCHull** allFactors;
 122 } AnalysisGraphsDataCHull;
 123
 124
 125 typedef struct
 126 {
 127         /* Point* hullArray[traceNb][traceNb][]
 128          *
 129          * A message comes from two traces. The lowest numbered trace is
 130          * considered to be the reference clock, CA. The other is CB. The
 131          * direction of messages (sent or received) is relative to CA. Points are
 132          * formed such that their abscissa comes from CA and their ordinate from
 133          * CB.
 134          *
 135          * hullArray is divided into three parts depending on the position of an
 136          * element hullArray[i][j]:
 137          *   Lower triangular part of the matrix
 138          *     i > j
 139          *     This contains the points that form lower hulls, therefore that
 140          *     represent "sent" messages.
 141          *   Upper triangular part of the matrix
 142          *     i < j
 143          *     This contains the points that form upper hulls, therefore that
 144          *     represent "received" messages.
 145          *   Diagonal part of the matrix
 146          *     i = j
 147          *     This contains empty lists
 148          *
 149          * When a message is such that:
 150          *   inE->traceNum < outE->traceNum
 151          *     CA is inE->traceNum, therefore the message was received and may
 152          *     generate a point in the upper hull. Upper hulls are such that i <
 153          *     j, therefore, i= inE->traceNum and j= outE->traceNum.
 154          *   inE->traceNum > outE->traceNum
 155          *     CA is outE->traceNum, therefore the message was sent and may
 156          *     generate a point in the lower hull. Lower hulls are such that i >
 157          *     j, therefore, i= inE->traceNum and j= outE->traceNum. Hence, we
 158          *     always have:
 159          *       i= inE->traceNum
 160          *       j= outE->traceNum
 161          *
 162          * Do not let yourself get confused! Always remember that the "lower hull"
 163          * is in fact the "lower half" of a hull. When assumptions are respected,
 164          * the lower half is above the upper half.
 165          */
 166         GQueue*** hullArray;
 167
 168         AnalysisStatsCHull* stats;
 169         AnalysisGraphsDataCHull* graphsData;
 170 } AnalysisDataCHull;
 171
 172 void registerAnalysisCHull();
 173
 174 FactorsCHull** calculateAllFactors(struct _SyncState* const syncState);
 175 void freeAllFactors(const unsigned int traceNb, FactorsCHull** const
 176         allFactors);
 177
 178 void calculateFactorsMiddle(FactorsCHull* const factors);
 179 void destroyFactorsCHull(FactorsCHull* factorsCHull);
 180
 181 #endif