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