RetainerSet.c 9.44 KB
Newer Older
1 2 3 4 5 6 7 8 9
/* -----------------------------------------------------------------------------
 *
 * (c) The GHC Team, 2001
 * Author: Sungwoo Park
 *
 * Retainer set implementation for retainer profiling (see RetainerProfile.c)
 *
 * ---------------------------------------------------------------------------*/

Ben Gamari's avatar
Ben Gamari committed
10
#if defined(PROFILING)
11

Simon Marlow's avatar
Simon Marlow committed
12
#include "PosixSource.h"
13
#include "Rts.h"
Simon Marlow's avatar
Simon Marlow committed
14

15 16 17 18 19
#include "Stats.h"
#include "RtsUtils.h"
#include "RetainerSet.h"
#include "Arena.h"
#include "Profiling.h"
20
#include "Trace.h"
21 22 23 24 25 26 27

#include <string.h>

#define HASH_TABLE_SIZE 255
#define hash(hk)  (hk % HASH_TABLE_SIZE)
static RetainerSet *hashTable[HASH_TABLE_SIZE];

28
static Arena *arena;            // arena in which we store retainer sets
29

30
static int nextId;              // id of next retainer set
31 32 33 34 35 36

/* -----------------------------------------------------------------------------
 * rs_MANY is a distinguished retainer set, such that
 *
 *        isMember(e, rs_MANY)   = True
 *
37 38
 *        addElement(e, rs)      = rs_MANY,   if rs->num >= maxRetainerSetSize
 *        addElement(e, rs_MANY) = rs_MANY
39 40 41 42 43
 *
 * The point of rs_MANY is to keep the total number of retainer sets
 * from growing too large.
 * -------------------------------------------------------------------------- */
RetainerSet rs_MANY = {
44 45 46 47 48
    .num     = 0,
    .hashKey = 0,
    .link    = NULL,
    .id      = 1,
    .element = {}
49 50 51 52 53
};

/* -----------------------------------------------------------------------------
 * calculate the size of a RetainerSet structure
 * -------------------------------------------------------------------------- */
sof's avatar
sof committed
54
STATIC_INLINE size_t
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
sizeofRetainerSet( int elems )
{
    return (sizeof(RetainerSet) + elems * sizeof(retainer));
}

/* -----------------------------------------------------------------------------
 * Creates the first pool and initializes hashTable[].
 * Frees all pools if any.
 * -------------------------------------------------------------------------- */
void
initializeAllRetainerSet(void)
{
    int i;

    arena = newArena();

    for (i = 0; i < HASH_TABLE_SIZE; i++)
72
        hashTable[i] = NULL;
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
    nextId = 2;   // Initial value must be positive, 2 is MANY.
}

/* -----------------------------------------------------------------------------
 * Frees all pools.
 * -------------------------------------------------------------------------- */
void
closeAllRetainerSet(void)
{
    arenaFree(arena);
}

/* -----------------------------------------------------------------------------
 *  Finds or creates if needed a singleton retainer set.
 * -------------------------------------------------------------------------- */
RetainerSet *
singleton(retainer r)
{
    RetainerSet *rs;
    StgWord hk;

    hk = hashKeySingleton(r);
    for (rs = hashTable[hash(hk)]; rs != NULL; rs = rs->link)
96
        if (rs->num == 1 &&  rs->element[0] == r) return rs;    // found it
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114

    // create it
    rs = arenaAlloc( arena, sizeofRetainerSet(1) );
    rs->num = 1;
    rs->hashKey = hk;
    rs->link = hashTable[hash(hk)];
    rs->id = nextId++;
    rs->element[0] = r;

    // The new retainer set is placed at the head of the linked list.
    hashTable[hash(hk)] = rs;

    return rs;
}

/* -----------------------------------------------------------------------------
 *   Finds or creates a retainer set *rs augmented with r.
 *   Invariants:
Ben Gamari's avatar
Ben Gamari committed
115
 *     r is not a member of rs, i.e., isMember(r, rs) returns false.
116 117 118 119 120 121 122 123 124
 *     rs is not NULL.
 *   Note:
 *     We could check if rs is NULL, in which case this function call
 *     reverts to singleton(). We do not choose this strategy because
 *     in most cases addElement() is invoked with non-NULL rs.
 * -------------------------------------------------------------------------- */
RetainerSet *
addElement(retainer r, RetainerSet *rs)
{
125 126
    uint32_t i;
    uint32_t nl;        // Number of retainers in *rs Less than r
127 128 129
    RetainerSet *nrs;   // New Retainer Set
    StgWord hk;         // Hash Key

130
    // debugBelch("addElement(%p, %p) = ", r, rs);
131 132

    ASSERT(rs != NULL);
133
    ASSERT(rs->num <= RtsFlags.ProfFlags.maxRetainerSetSize);
134

135
    if (rs == &rs_MANY || rs->num == RtsFlags.ProfFlags.maxRetainerSetSize) {
136
        return &rs_MANY;
137 138 139 140 141
    }

    ASSERT(!isMember(r, rs));

    for (nl = 0; nl < rs->num; nl++)
142
        if (r < rs->element[nl]) break;
143 144 145 146 147 148 149
    // Now nl is the index for r into the new set.
    // Also it denotes the number of retainers less than r in *rs.
    // Thus, compare the first nl retainers, then r itself, and finally the
    // remaining (rs->num - nl) retainers.

    hk = hashKeyAddElement(r, rs);
    for (nrs = hashTable[hash(hk)]; nrs != NULL; nrs = nrs->link) {
150
        // test *rs and *nrs for equality
151

152 153
        // check their size
        if (rs->num + 1 != nrs->num) continue;
154

155 156 157 158
        // compare the first nl retainers and find the first non-matching one.
        for (i = 0; i < nl; i++)
            if (rs->element[i] != nrs->element[i]) break;
        if (i < nl) continue;
159

160 161
        // compare r itself
        if (r != nrs->element[i]) continue;       // i == nl
162

163 164 165 166
        // compare the remaining retainers
        for (; i < rs->num; i++)
            if (rs->element[i] != nrs->element[i + 1]) break;
        if (i < rs->num) continue;
167

168
        // debugBelch("%p\n", nrs);
169

170 171
        // The set we are seeking already exists!
        return nrs;
172 173 174 175 176 177 178 179 180
    }

    // create a new retainer set
    nrs = arenaAlloc( arena, sizeofRetainerSet(rs->num + 1) );
    nrs->num = rs->num + 1;
    nrs->hashKey = hk;
    nrs->link = hashTable[hash(hk)];
    nrs->id = nextId++;
    for (i = 0; i < nl; i++) {              // copy the first nl retainers
181
        nrs->element[i] = rs->element[i];
182 183 184
    }
    nrs->element[i] = r;                    // copy r
    for (; i < rs->num; i++) {              // copy the remaining retainers
185
        nrs->element[i + 1] = rs->element[i];
186 187 188 189
    }

    hashTable[hash(hk)] = nrs;

190
    // debugBelch("%p\n", nrs);
191 192 193 194 195 196 197
    return nrs;
}

/* -----------------------------------------------------------------------------
 *  printRetainer() prints the full information on a given retainer,
 *  not a retainer set.
 * -------------------------------------------------------------------------- */
198
static void
199 200 201 202 203 204 205 206 207 208
printRetainer(FILE *f, retainer ccs)
{
    fprintCCS(f, ccs);
}

/* -----------------------------------------------------------------------------
 *  printRetainerSetShort() should always display the same output for
 *  a given retainer set regardless of the time of invocation.
 * -------------------------------------------------------------------------- */
void
209
printRetainerSetShort(FILE *f, RetainerSet *rs, W_ total_size, uint32_t max_length)
210
{
211
    char tmp[max_length + 1];
212 213
    uint32_t size;
    uint32_t j;
214 215 216

    ASSERT(rs->id < 0);

217
    tmp[max_length] = '\0';
218 219 220 221

    // No blank characters are allowed.
    sprintf(tmp + 0, "(%d)", -(rs->id));
    size = strlen(tmp);
222
    ASSERT(size < max_length);
223 224

    for (j = 0; j < rs->num; j++) {
225 226 227 228 229 230 231 232 233 234 235 236 237 238
        if (j < rs->num - 1) {
            strncpy(tmp + size, rs->element[j]->cc->label, max_length - size);
            size = strlen(tmp);
            if (size == max_length)
                break;
            strncpy(tmp + size, ",", max_length - size);
            size = strlen(tmp);
            if (size == max_length)
                break;
        }
        else {
            strncpy(tmp + size, rs->element[j]->cc->label, max_length - size);
            // size = strlen(tmp);
        }
239
    }
240
    fputs(tmp, f);
241
    traceHeapProfSampleString(0, tmp, total_size);
242 243 244
}

/* -----------------------------------------------------------------------------
245 246 247
 * Dump the contents of each retainer set into the log file at the end
 * of the run, so the user can find out for a given retainer set ID
 * the full contents of that set.
248
 * -------------------------------------------------------------------------- */
249 250 251
void
outputAllRetainerSet(FILE *prof_file)
{
252 253
    uint32_t i, j;
    uint32_t numSet;
254 255 256 257 258 259
    RetainerSet *rs, **rsArray, *tmp;

    // find out the number of retainer sets which have had a non-zero cost at
    // least once during retainer profiling
    numSet = 0;
    for (i = 0; i < HASH_TABLE_SIZE; i++)
260 261 262 263
        for (rs = hashTable[i]; rs != NULL; rs = rs->link) {
            if (rs->id < 0)
                numSet++;
        }
264 265

    if (numSet == 0)      // retainer profiling was not done at all.
266
        return;
267 268 269

    // allocate memory
    rsArray = stgMallocBytes(numSet * sizeof(RetainerSet *),
270
                             "outputAllRetainerSet()");
271 272 273 274

    // prepare for sorting
    j = 0;
    for (i = 0; i < HASH_TABLE_SIZE; i++)
275 276 277 278 279 280
        for (rs = hashTable[i]; rs != NULL; rs = rs->link) {
            if (rs->id < 0) {
                rsArray[j] = rs;
                j++;
            }
        }
281 282 283 284 285

    ASSERT(j == numSet);

    // sort rsArray[] according to the id of each retainer set
    for (i = numSet - 1; i > 0; i--) {
286 287 288 289 290 291 292 293
        for (j = 0; j <= i - 1; j++) {
            // if (-(rsArray[j]->id) < -(rsArray[j + 1]->id))
            if (rsArray[j]->id < rsArray[j + 1]->id) {
                tmp = rsArray[j];
                rsArray[j] = rsArray[j + 1];
                rsArray[j + 1] = tmp;
            }
        }
294 295 296 297
    }

    fprintf(prof_file, "\nRetainer sets created during profiling:\n");
    for (i = 0;i < numSet; i++) {
298 299 300 301 302 303 304
        fprintf(prof_file, "SET %u = {", -(rsArray[i]->id));
        for (j = 0; j < rsArray[i]->num - 1; j++) {
            printRetainer(prof_file, rsArray[i]->element[j]);
            fprintf(prof_file, ", ");
        }
        printRetainer(prof_file, rsArray[i]->element[j]);
        fprintf(prof_file, "}\n");
305 306
    }

sof's avatar
sof committed
307
    stgFree(rsArray);
308 309 310
}

#endif /* PROFILING */