lttv/lttv/sync/event_analysis_chull.h

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