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
|
/* -----------------------------------------------------------------------------
*
* (c) The GHC Team, 1998-2018
*
* Non-moving garbage collector and allocator: Mark phase
*
* ---------------------------------------------------------------------------*/
#pragma once
#include "Hash.h"
#include "Task.h"
#include "NonMoving.h"
#include "BeginPrivate.h"
#include "Hash.h"
enum EntryType {
NULL_ENTRY = 0,
MARK_CLOSURE,
MARK_ARRAY
};
/* Note [Origin references in the nonmoving collector]
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* To implement indirection short-cutting and the selector optimisation the
* collector needs to know where it found references, so it can update the
* reference if it later turns out that points to an indirection. For this
* reason, each mark queue entry contains two things:
*
* - a pointer to the object to be marked (p), and
*
* - a pointer to the field where we found the reference (origin)
*
* Note that the origin pointer is an interior pointer: it points not to a
* valid closure (with info table pointer) but rather to a field inside a closure.
* Since such references can't be safely scavenged we establish the invariant
* that the origin pointer may only point to a field of an object living in the
* nonmoving heap, where no scavenging is needed.
*
*/
typedef struct {
enum EntryType type;
// All pointers should be untagged
union {
struct {
StgClosure *p; // the object to be marked
StgClosure **origin; // field where this reference was found.
// See Note [Origin references in the nonmoving collector]
} mark_closure;
struct {
const StgMutArrPtrs *array;
StgWord start_index;
} mark_array;
};
} MarkQueueEnt;
typedef struct {
// index of first *unused* queue entry
uint32_t head;
MarkQueueEnt entries[];
} MarkQueueBlock;
/* The mark queue is not capable of concurrent read or write.
*
* invariants:
*
* a. top == blocks->start;
* b. there is always a valid MarkQueueChunk, although it may be empty
* (e.g. top->head == 0).
*/
typedef struct MarkQueue_ {
// A singly link-list of blocks, each containing a MarkQueueChunk.
bdescr *blocks;
// Cached value of blocks->start.
MarkQueueBlock *top;
// Is this a mark queue or a capability-local update remembered set?
bool is_upd_rem_set;
// Marked objects outside of nonmoving heap, namely large and static
// objects.
HashTable *marked_objects;
} MarkQueue;
/* While it shares its representation with MarkQueue, UpdRemSet differs in
* behavior when pushing; namely full chunks are immediately pushed to the
* global update remembered set, not accumulated into a chain. We make this
* distinction apparent in the types.
*/
typedef struct {
MarkQueue queue;
} UpdRemSet;
// The length of MarkQueueBlock.entries
#define MARK_QUEUE_BLOCK_ENTRIES ((BLOCK_SIZE - sizeof(MarkQueueBlock)) / sizeof(MarkQueueEnt))
extern bdescr *nonmoving_large_objects, *nonmoving_marked_large_objects;
extern memcount n_nonmoving_large_blocks, n_nonmoving_marked_large_blocks;
extern StgTSO *nonmoving_old_threads;
extern StgWeak *nonmoving_old_weak_ptr_list;
extern StgTSO *nonmoving_threads;
extern StgWeak *nonmoving_weak_ptr_list;
#if defined(DEBUG)
extern StgIndStatic *debug_caf_list_snapshot;
#endif
extern MarkQueue *current_mark_queue;
extern bdescr *upd_rem_set_block_list;
void nonmovingMarkInitUpdRemSet(void);
void init_upd_rem_set(UpdRemSet *rset);
void reset_upd_rem_set(UpdRemSet *rset);
void updateRemembSetPushThunk(Capability *cap, StgThunk *p);
void updateRemembSetPushTSO(Capability *cap, StgTSO *tso);
void updateRemembSetPushStack(Capability *cap, StgStack *stack);
#if defined(THREADED_RTS)
void nonmovingFlushCapUpdRemSetBlocks(Capability *cap);
void nonmovingBeginFlush(Task *task);
bool nonmovingWaitForFlush(void);
void nonmovingFinishFlush(Task *task);
#endif
void markQueueAddRoot(MarkQueue* q, StgClosure** root);
void initMarkQueue(MarkQueue *queue);
void freeMarkQueue(MarkQueue *queue);
void nonmovingMark(struct MarkQueue_ *restrict queue);
bool nonmovingTidyWeaks(struct MarkQueue_ *queue);
void nonmovingTidyThreads(void);
void nonmovingMarkDeadWeaks(struct MarkQueue_ *queue, StgWeak **dead_weak_ptr_list);
void nonmovingResurrectThreads(struct MarkQueue_ *queue, StgTSO **resurrected_threads);
bool nonmovingIsAlive(StgClosure *p);
void nonmovingMarkDeadWeak(struct MarkQueue_ *queue, StgWeak *w);
void nonmovingMarkLiveWeak(struct MarkQueue_ *queue, StgWeak *w);
void markQueuePush(MarkQueue *q, const MarkQueueEnt *ent);
void markQueuePushClosure(MarkQueue *q,
StgClosure *p,
StgClosure **origin);
void markQueuePushClosure_(MarkQueue *q, StgClosure *p);
void markQueuePushThunkSrt(MarkQueue *q, const StgInfoTable *info);
void markQueuePushFunSrt(MarkQueue *q, const StgInfoTable *info);
void markQueuePushArray(MarkQueue *q, const StgMutArrPtrs *array, StgWord start_index);
void updateRemembSetPushThunkEager(Capability *cap,
const StgThunkInfoTable *orig_info,
StgThunk *thunk);
INLINE_HEADER bool markQueueIsEmpty(MarkQueue *q)
{
return (q->blocks == NULL) || (q->top->head == 0 && q->blocks->link == NULL);
}
#if defined(DEBUG)
void printMarkQueueEntry(MarkQueueEnt *ent);
void printMarkQueue(MarkQueue *q);
#endif
#include "EndPrivate.h"
|
