ghc/rts/RetainerSet.h

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