ghc/rts/RetainerSet.h

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team, 2001
   4  * Author: Sungwoo Park
   5  *
   6  * Retainer set interface for retainer profiling.
   7  *
   8  * ---------------------------------------------------------------------------*/
   9
  10 #ifndef RETAINERSET_H
  11 #define RETAINERSET_H
  12
  13 #include <stdio.h>
  14
  15 #ifdef PROFILING
  16
  17 /*
  18   Type 'retainer' defines the retainer identity.
  19
  20   Invariant:
  21     1. The retainer identity of a given retainer cannot change during
  22     program execution, no matter where it is actually stored.
  23     For instance, the memory address of a retainer cannot be used as
  24     its retainer identity because its location may change during garbage
  25     collections.
  26     2. Type 'retainer' must come with comparison operations as well as
  27     an equality operation. That it, <, >, and == must be supported -
  28     this is necessary to store retainers in a sorted order in retainer sets.
  29     Therefore, you cannot use a huge structure type as 'retainer', for instance.
  30
  31   We illustrate three possibilities of defining 'retainer identity'.
  32   Choose one of the following three compiler directives:
  33
  34    Retainer scheme 1 (RETAINER_SCHEME_INFO) : retainer = info table
  35    Retainer scheme 2 (RETAINER_SCHEME_CCS)  : retainer = cost centre stack
  36    Retainer scheme 3 (RETAINER_SCHEME_CC)   : retainer = cost centre
  37 */
  38
  39 // #define RETAINER_SCHEME_INFO
  40 #define RETAINER_SCHEME_CCS
  41 // #define RETAINER_SCHEME_CC
  42
  43 #ifdef RETAINER_SCHEME_INFO
  44 struct _StgInfoTable;
  45 typedef struct _StgInfoTable *retainer;
  46 #endif
  47
  48 #ifdef RETAINER_SCHEME_CCS
  49 typedef CostCentreStack *retainer;
  50 #endif
  51
  52 #ifdef RETAINER_SCHEME_CC
  53 typedef CostCentre *retainer;
  54 #endif
  55
  56 /*
  57   Type 'retainerSet' defines an abstract datatype for sets of retainers.
  58
  59   Invariants:
  60     A retainer set stores its elements in increasing order (in element[] array).
  61  */
  62
  63 typedef struct _RetainerSet {
  64   nat num;                      // number of elements
  65   StgWord hashKey;              // hash key for this retainer set
  66   struct _RetainerSet *link;    // link to the next retainer set in the bucket
  67   int id;   // unique id of this retainer set (used when printing)
  68             // Its absolute value is interpreted as its true id; if id is
  69             // negative, it indicates that this retainer set has had a postive
  70             // cost after some retainer profiling.
  71   retainer element[0];          // elements of this retainer set
  72   // do not put anything below here!
  73 } RetainerSet;
  74
  75 /*
  76   Note:
  77     There are two ways of maintaining all retainer sets. The first is simply by
  78     freeing all the retainer sets and re-initialize the hash table at each
  79     retainer profiling. The second is by setting the cost field of each
  80     retainer set. The second is preferred to the first if most retainer sets
  81     are likely to be observed again during the next retainer profiling. Note
  82     that in the first approach, we do not free the memory allocated for
  83     retainer sets; we just invalidate all retainer sets.
  84  */
  85 #ifdef DEBUG_RETAINER
  86 // In thise case, FIRST_APPROACH must be turned on because the memory pool
  87 // for retainer sets is freed each time.
  88 #define FIRST_APPROACH
  89 #else
  90 // #define FIRST_APPROACH
  91 #define SECOND_APPROACH
  92 #endif
  93
  94 // Creates the first pool and initializes a hash table. Frees all pools if any.
  95 void initializeAllRetainerSet(void);
  96
  97 // Refreshes all pools for reuse and initializes a hash table.
  98 void refreshAllRetainerSet(void);
  99
 100 // Frees all pools.
 101 void closeAllRetainerSet(void);
 102
 103 // Finds or creates if needed a singleton retainer set.
 104 RetainerSet *singleton(retainer r);
 105
 106 extern RetainerSet rs_MANY;
 107
 108 // Checks if a given retainer is a memeber of the retainer set.
 109 //
 110 // Note & (maybe) Todo:
 111 //   This function needs to be declared as an inline function, so it is declared
 112 //   as an inline static function here.
 113 //   This make the interface really bad, but isMember() returns a value, so
 114 //   it is not easy either to write it as a macro (due to my lack of C
 115 //   programming experience). Sungwoo
 116 //
 117 // rtsBool isMember(retainer, retainerSet *);
 118 /*
 119   Returns rtsTrue if r is a member of *rs.
 120   Invariants:
 121     rs is not NULL.
 122   Note:
 123     The efficiency of this function is subject to the typical size of
 124     retainer sets. If it is small, linear scan is better. If it
 125     is large in most cases, binary scan is better.
 126     The current implementation mixes the two search strategies.
 127  */
 128
 129 #define BINARY_SEARCH_THRESHOLD   8
 130 static inline rtsBool
 131 isMember(retainer r, RetainerSet *rs)
 132 {
 133   int i, left, right;       // must be int, not nat (because -1 can appear)
 134   retainer ri;
 135
 136   if (rs == &rs_MANY) { return rtsTrue; }
 137
 138   if (rs->num < BINARY_SEARCH_THRESHOLD) {
 139     for (i = 0; i < (int)rs->num; i++) {
 140       ri = rs->element[i];
 141       if (r == ri) return rtsTrue;
 142       else if (r < ri) return rtsFalse;
 143     }
 144   } else {
 145     left = 0;
 146     right = rs->num - 1;
 147     while (left <= right) {
 148       i = (left + right) / 2;
 149       ri = rs->element[i];
 150       if (r == ri) return rtsTrue;
 151       else if (r < ri) right = i - 1;
 152       else left = i + 1;
 153     }
 154   }
 155   return rtsFalse;
 156 }
 157
 158 // Finds or creates a retainer set augmented with a new retainer.
 159 RetainerSet *addElement(retainer, RetainerSet *);
 160
 161 // Call f() for each retainer set.
 162 void traverseAllRetainerSet(void (*f)(RetainerSet *));
 163
 164 #ifdef SECOND_APPROACH
 165 // Prints a single retainer set.
 166 void printRetainerSetShort(FILE *, RetainerSet *);
 167 #endif
 168
 169 // Print the statistics on all the retainer sets.
 170 // store the sum of all costs and the number of all retainer sets.
 171 void outputRetainerSet(FILE *, nat *, nat *);
 172
 173 #ifdef SECOND_APPROACH
 174 // Print all retainer sets at the exit of the program.
 175 void outputAllRetainerSet(FILE *);
 176 #endif
 177
 178 // Hashing functions
 179 /*
 180   Invariants:
 181     Once either initializeAllRetainerSet() or refreshAllRetainerSet()
 182     is called, there exists only one copy of any retainer set created
 183     through singleton() and addElement().  The pool (the storage for
 184     retainer sets) is consumed linearly.  All the retainer sets of the
 185     same hash function value are linked together from an element in
 186     hashTable[].  See the invariants of allocateInPool() for the
 187     maximum size of retainer sets.  The hashing function is defined by
 188     hashKeySingleton() and hashKeyAddElement(). The hash key for a set
 189     must be unique regardless of the order its elements are inserted,
 190     i.e., the hashing function must be additive(?).
 191 */
 192 #define hashKeySingleton(r)       ((StgWord)(r))
 193 #define hashKeyAddElement(r, s)   (hashKeySingleton((r)) + (s)->hashKey)
 194
 195 // Prints the full information on a given retainer.
 196 // Note: This function is not part of retainerSet interface, but this is
 197 //       the best place to define it.
 198 void printRetainer(FILE *, retainer);
 199
 200 #endif // PROFILING
 201 #endif // RETAINERSET_H