summaryrefslogtreecommitdiff
path: root/rts/TraverseHeap.h
blob: 010b2f302506d64d3ceabc53465c2deea757f833 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
/* -----------------------------------------------------------------------------
 *
 * (c) The GHC Team, 2019
 * Author: Daniel Gröber
 *
 * Generalised profiling heap traversal.
 *
 * ---------------------------------------------------------------------------*/

#pragma once

#if defined(PROFILING)

#include <rts/Types.h>
#include "RetainerSet.h"

#include "BeginPrivate.h"

typedef enum {
    // Object with fixed layout. Keeps an information about that
    // element was processed. (stackPos.next.step)
    posTypeStep,
    // Description of the pointers-first heap object. Keeps information
    // about layout. (stackPos.next.ptrs)
    posTypePtrs,
    // Keeps SRT bitmap (stackPos.next.srt)
    posTypeSRT,
    // Keeps a new object that was not inspected yet. Keeps a parent
    // element (stackPos.next.parent)
    posTypeFresh,
    // This stackElement is empty
    posTypeEmpty
} nextPosType;

typedef union {
    // fixed layout or layout specified by a field in the closure
    StgWord step;

    // layout.payload
    struct {
        // See StgClosureInfo in InfoTables.h
        StgHalfWord pos;
        StgHalfWord ptrs;
        StgPtr payload;
    } ptrs;

    // SRT
    struct {
        StgClosure *srt;
    } srt;

    // parent of the current closure, used only when posTypeFresh is set
    StgClosure *cp;
} nextPos;

/**
 * Position pointer into a closure. Determines what the next element to return
 * for a stackElement is.
 */
typedef struct stackPos_ {
    nextPosType type;
    nextPos next;
} stackPos;

typedef union stackData_ {
     /**
      * Most recent retainer for the corresponding closure on the stack.
      */
    retainer c_child_r;
} stackData;

extern const stackData nullStackData;

typedef union stackAccum_ {
    StgWord subtree_sizeW;
} stackAccum;

/**
 * An element of the traversal work-stack. Besides the closure itself this also
 * stores it's parent, associated data and an accumulator.
 *
 * When 'info.type == posTypeFresh' a 'stackElement' represents just one
 * closure, namely 'c' and 'cp' being it's parent. Otherwise 'info' specifies an
 * offset into the children of 'c'. This is to support returning a closure's
 * children one-by-one without pushing one element per child onto the stack. See
 * traverseGetChildren() and traversePop().
 *
 */
typedef struct stackElement_ {
    stackPos info;
    StgClosure *c;
    struct stackElement_ *sep; // stackElement of parent closure
    stackData data;
    stackAccum accum;
} stackElement;

typedef struct traverseState_ {
    /** Note [Profiling heap traversal visited bit]
     * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     * If the RTS is compiled with profiling enabled StgProfHeader can be used
     * by profiling code to store per-heap object information. Specifically the
     * 'hp_hdr' field is used to store heap profiling information.
     *
     * The generic heap traversal code reserves the least significant bit of the
     * heap profiling word to decide whether we've already visited a given
     * closure in the current pass or not. The rest of the field is free to be
     * used by the calling profiler.
     *
     * By doing things this way we implicitly assume that the LSB is not used by
     * the user. This is true at least for the word aligned pointers which the
     * retainer profiler currently stores there and should be maintained by new
     * users for example by shifting the real data up by one bit.
     *
     * Since we don't want to have to scan the entire heap a second time just to
     * reset the per-object visited bit before/after the real traversal we make
     * the interpretation of this bit dependent on the value of a global
     * variable, 'flip' and "flip" this variable when we want to invalidate all
     * objects.
     *
     * When the visited bit is equal to the value of 'flip' the closure data is
     * valid otherwise not (see isTravDataValid). Both the value of the closure
     * and global 'flip' value start out as zero, so all closures are considered
     * valid. Before every traversal we invert the value of 'flip' (see
     * traverseInvalidateClosureData) invalidating all closures.
     *
     * There are some complications with this approach, namely: static objects
     * and mutable data. There we do just go over all existing objects to reset
     * the bit manually. See 'resetStaticObjectForProfiling' and
     * 'resetMutableObjects'.
     */
    StgWord flip;

    /**
     * Invariants:
     *
     *    firstStack points to the first block group.
     *
     *    currentStack points to the block group currently being used.
     *
     *    currentStack->free == stackLimit.
     *
     *    stackTop points to the topmost byte in the stack of currentStack.
     *
     *    Unless the whole stack is empty, stackTop must point to the topmost
     *    object (or byte) in the whole stack. Thus, it is only when the whole
     *    stack is empty that stackTop == stackLimit (not during the execution
     *    of pushStackElement() and popStackElement()).
     *
     *    stackBottom == currentStack->start.
     *
     *    stackLimit
     *      == currentStack->start + BLOCK_SIZE_W * currentStack->blocks.
     *
     *  Note:
     *
     *    When a current stack becomes empty, stackTop is set to point to
     *    the topmost element on the previous block group so as to satisfy
     *    the invariants described above.
     */
    bdescr *firstStack;
    bdescr *currentStack;
    stackElement *stackBottom, *stackTop, *stackLimit;

    /**
     * stackSize: records the current size of the stack.
     * maxStackSize: records its high water mark.
     *
     * Invariants:
     *
     *   stackSize <= maxStackSize
     *
     * Note:
     *
     *   When return_cb == NULL stackSize is just an estimate measure of the
     *   depth of the graph. The reason is that some heap objects have only a
     *   single child and may not result in a new element being pushed onto the
     *   stack. Therefore, at the end of retainer profiling, maxStackSize is
     *   some value no greater than the actual depth of the graph.
     */
    int stackSize, maxStackSize;

    /**
     * Callback called when processing of a closure 'c' is complete, i.e. when
     * all it's children have been processed. Note: This includes leaf nodes
     * without children.
     *
     * @param c     The closure who's processing just completed.
     * @param acc   The current value of the accumulator for 'c' on the
     *              stack. It's about to be removed, hence the 'const'
     *              qualifier. This is the same accumulator 'visit_cb' got
     *              passed when 'c' was visited.
     *
     * @param c_parent    The parent closure of 'c'
     * @param acc_parent  The accumulator associated with 'c_parent', currently
     *                    on the stack.
     */
    void (*return_cb)(StgClosure *c, const stackAccum acc,
                      StgClosure *c_parent, stackAccum *acc_parent);
} traverseState;

/**
 * Callback called when heap traversal visits a closure.
 *
 * The callback can assume that the closure's profiling data has been
 * initialized to zero if this is the first visit during a pass.
 *
 * See Note [Profiling heap traversal visited bit].
 *
 * Returning 'false' will instruct the heap traversal code to skip processing
 * this closure's children. If you don't need to traverse any closure more than
 * once you can simply return 'first_visit'.
 */
typedef bool (*visitClosure_cb) (
    StgClosure *c,
    const StgClosure *cp,
    const stackData data,
    const bool first_visit,
    stackAccum *accum,
    stackData *child_data);

StgWord getTravData(const StgClosure *c);
void setTravData(const traverseState *ts, StgClosure *c, StgWord w);
bool isTravDataValid(const traverseState *ts, const StgClosure *c);

void traverseWorkStack(traverseState *ts, visitClosure_cb visit_cb);
void traversePushRoot(traverseState *ts, StgClosure *c, StgClosure *cp, stackData data);
void traversePushClosure(traverseState *ts, StgClosure *c, StgClosure *cp, stackElement *sep, stackData data);
bool traverseMaybeInitClosureData(const traverseState* ts, StgClosure *c);
void traverseInvalidateClosureData(traverseState* ts);

void initializeTraverseStack(traverseState *ts);
void closeTraverseStack(traverseState *ts);
int getTraverseStackMaxSize(traverseState *ts);

// for GC.c
W_ traverseWorkStackBlocks(traverseState *ts);
void resetStaticObjectForProfiling(const traverseState *ts, StgClosure *static_objects);

#include "EndPrivate.h"

#endif /* PROFILING */