diff options
Diffstat (limited to 'rts/RetainerSet.h')
| -rw-r--r-- | rts/RetainerSet.h | 201 |
1 files changed, 201 insertions, 0 deletions
diff --git a/rts/RetainerSet.h b/rts/RetainerSet.h new file mode 100644 index 0000000000..6a00e1395e --- /dev/null +++ b/rts/RetainerSet.h @@ -0,0 +1,201 @@ +/* ----------------------------------------------------------------------------- + * + * (c) The GHC Team, 2001 + * Author: Sungwoo Park + * + * Retainer set interface for retainer profiling. + * + * ---------------------------------------------------------------------------*/ + +#ifndef RETAINERSET_H +#define RETAINERSET_H + +#include <stdio.h> + +#ifdef PROFILING + +/* + Type 'retainer' defines the retainer identity. + + Invariant: + 1. The retainer identity of a given retainer cannot change during + program execution, no matter where it is actually stored. + For instance, the memory address of a retainer cannot be used as + its retainer identity because its location may change during garbage + collections. + 2. Type 'retainer' must come with comparison operations as well as + an equality operation. That it, <, >, and == must be supported - + this is necessary to store retainers in a sorted order in retainer sets. + Therefore, you cannot use a huge structure type as 'retainer', for instance. + + We illustrate three possibilities of defining 'retainer identity'. + Choose one of the following three compiler directives: + + Retainer scheme 1 (RETAINER_SCHEME_INFO) : retainer = info table + Retainer scheme 2 (RETAINER_SCHEME_CCS) : retainer = cost centre stack + Retainer scheme 3 (RETAINER_SCHEME_CC) : retainer = cost centre +*/ + +// #define RETAINER_SCHEME_INFO +#define RETAINER_SCHEME_CCS +// #define RETAINER_SCHEME_CC + +#ifdef RETAINER_SCHEME_INFO +struct _StgInfoTable; +typedef struct _StgInfoTable *retainer; +#endif + +#ifdef RETAINER_SCHEME_CCS +typedef CostCentreStack *retainer; +#endif + +#ifdef RETAINER_SCHEME_CC +typedef CostCentre *retainer; +#endif + +/* + Type 'retainerSet' defines an abstract datatype for sets of retainers. + + Invariants: + A retainer set stores its elements in increasing order (in element[] array). + */ + +typedef struct _RetainerSet { + nat num; // number of elements + StgWord hashKey; // hash key for this retainer set + struct _RetainerSet *link; // link to the next retainer set in the bucket + int id; // unique id of this retainer set (used when printing) + // Its absolute value is interpreted as its true id; if id is + // negative, it indicates that this retainer set has had a postive + // cost after some retainer profiling. + retainer element[0]; // elements of this retainer set + // do not put anything below here! +} RetainerSet; + +/* + Note: + There are two ways of maintaining all retainer sets. The first is simply by + freeing all the retainer sets and re-initialize the hash table at each + retainer profiling. The second is by setting the cost field of each + retainer set. The second is preferred to the first if most retainer sets + are likely to be observed again during the next retainer profiling. Note + that in the first approach, we do not free the memory allocated for + retainer sets; we just invalidate all retainer sets. + */ +#ifdef DEBUG_RETAINER +// In thise case, FIRST_APPROACH must be turned on because the memory pool +// for retainer sets is freed each time. +#define FIRST_APPROACH +#else +// #define FIRST_APPROACH +#define SECOND_APPROACH +#endif + +// Creates the first pool and initializes a hash table. Frees all pools if any. +void initializeAllRetainerSet(void); + +// Refreshes all pools for reuse and initializes a hash table. +void refreshAllRetainerSet(void); + +// Frees all pools. +void closeAllRetainerSet(void); + +// Finds or creates if needed a singleton retainer set. +RetainerSet *singleton(retainer r); + +extern RetainerSet rs_MANY; + +// Checks if a given retainer is a memeber of the retainer set. +// +// Note & (maybe) Todo: +// This function needs to be declared as an inline function, so it is declared +// as an inline static function here. +// This make the interface really bad, but isMember() returns a value, so +// it is not easy either to write it as a macro (due to my lack of C +// programming experience). Sungwoo +// +// rtsBool isMember(retainer, retainerSet *); +/* + Returns rtsTrue if r is a member of *rs. + Invariants: + rs is not NULL. + Note: + The efficiency of this function is subject to the typical size of + retainer sets. If it is small, linear scan is better. If it + is large in most cases, binary scan is better. + The current implementation mixes the two search strategies. + */ + +#define BINARY_SEARCH_THRESHOLD 8 +INLINE_HEADER rtsBool +isMember(retainer r, RetainerSet *rs) +{ + int i, left, right; // must be int, not nat (because -1 can appear) + retainer ri; + + if (rs == &rs_MANY) { return rtsTrue; } + + if (rs->num < BINARY_SEARCH_THRESHOLD) { + for (i = 0; i < (int)rs->num; i++) { + ri = rs->element[i]; + if (r == ri) return rtsTrue; + else if (r < ri) return rtsFalse; + } + } else { + left = 0; + right = rs->num - 1; + while (left <= right) { + i = (left + right) / 2; + ri = rs->element[i]; + if (r == ri) return rtsTrue; + else if (r < ri) right = i - 1; + else left = i + 1; + } + } + return rtsFalse; +} + +// Finds or creates a retainer set augmented with a new retainer. +RetainerSet *addElement(retainer, RetainerSet *); + +// Call f() for each retainer set. +void traverseAllRetainerSet(void (*f)(RetainerSet *)); + +#ifdef SECOND_APPROACH +// Prints a single retainer set. +void printRetainerSetShort(FILE *, RetainerSet *); +#endif + +// Print the statistics on all the retainer sets. +// store the sum of all costs and the number of all retainer sets. +void outputRetainerSet(FILE *, nat *, nat *); + +#ifdef SECOND_APPROACH +// Print all retainer sets at the exit of the program. +void outputAllRetainerSet(FILE *); +#endif + +// Hashing functions +/* + Invariants: + Once either initializeAllRetainerSet() or refreshAllRetainerSet() + is called, there exists only one copy of any retainer set created + through singleton() and addElement(). The pool (the storage for + retainer sets) is consumed linearly. All the retainer sets of the + same hash function value are linked together from an element in + hashTable[]. See the invariants of allocateInPool() for the + maximum size of retainer sets. The hashing function is defined by + hashKeySingleton() and hashKeyAddElement(). The hash key for a set + must be unique regardless of the order its elements are inserted, + i.e., the hashing function must be additive(?). +*/ +#define hashKeySingleton(r) ((StgWord)(r)) +#define hashKeyAddElement(r, s) (hashKeySingleton((r)) + (s)->hashKey) + +// Prints the full information on a given retainer. +// Note: This function is not part of retainerSet interface, but this is +// the best place to define it. +void printRetainer(FILE *, retainer); + +#endif /* PROFILING */ +#endif /* RETAINERSET_H */ |