Reorganisation of the source tree
[ghc.git] / 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 INLINE_HEADER 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 */