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