ghc/rts/RetainerSet.h

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