1#include "include/pw.h"
2#include "src/types/compound_internal.h"
3
4#define get_this_cdata(value) _pw_get_this_struct_ptr(_PwCompoundData*, mthis, (value))
5
6[[nodiscard]] PwValuePtr _pw_value_is_on_chain(PwValuePtr value, _PwCompoundChain* tail)
7{
8 do {
9 if (value->struct_data == tail->value->struct_data) {
10 return tail->value;
11 }
12 tail = tail->prev;
13 } while (tail);
14 return nullptr;
15}
16
17/****************************************************************
18 * Basic interface
19 */
20
21static bool compound_create(PwMethod_Basic_create* mthis, PwValuePtr result, PwCtorArgs* ctor_args)
22{
23 if (!pw_super(mthis, result, ctor_args)) {
24 return false;
25 }
26
27 _PwCompoundData* cdata = get_this_cdata(result);
28
29 _pw_atomic_store(&cdata->set_refcount, 1);
30 cdata->set_refcount_ptr = &cdata->set_refcount;
31 return true;
32}
33
34static bool compound_destroy(PwMethod_Basic_destroy* mthis, PwValuePtr self, _PwCompoundChain* tail)
35{
36 PwValuePtr value_seen = _pw_on_chain(self, tail);
37 if (value_seen) {
38 return true;
39 }
40 return pw_super(mthis, self, nullptr);
41}
42
43static bool compound_clone(PwMethod_Basic_clone* mthis, PwValuePtr self)
44{
45 /*
46 * Clone compound: increase set_refcount along with refcount.
47 * We decrement set_refcount in _pw_compound_join which immediatelly follows clone (or deepcopy).
48 */
49
50 // XXX copy-pasted from Struct to avoid super call
51
52 _PwStructData* struct_data = (_PwStructData*) self->struct_data;
53 _pw_atomic_add(&struct_data->refcount, 1);
54
55 // increment set_refcount
56
57 _PwCompoundData* cdata = get_this_cdata(self);
58 _pw_atomic_add(cdata->set_refcount_ptr, 1);
59 return true;
60}
61
62static bool compound_decref(PwMethod_Basic_decref* mthis, PwValuePtr self)
63{
64 // XXX copy-pasted from Struct to avoid super call
65
66 _PwStructData* struct_data = (_PwStructData*) self->struct_data;
67 _pw_atomic_sub(&struct_data->refcount, 1);
68
69 // decrement set_refcount
70
71 _PwCompoundData* cdata = get_this_cdata(self);
72
73 unsigned prev_refcount = atomic_fetch_sub_explicit(cdata->set_refcount_ptr, 1, memory_order_relaxed);
74 if (prev_refcount == 0) {
75 // allow set_refcount underflow, which means destruction is in progress
76 // just keep it zero
77 atomic_fetch_add_explicit(cdata->set_refcount_ptr, 1, memory_order_relaxed);
78 prev_refcount = 1;
79 }
80 return prev_refcount != 1;
81}
82
83static bool compound_dump(PwMethod_Basic_dump* mthis, PwValuePtr self, FILE* fp, int indent, _PwCompoundChain* tail)
84{
85 PwValuePtr value_seen = _pw_on_chain(self, tail);
86 if (value_seen) {
87 _pw_print_indent(fp, indent + 4);
88 fprintf(fp, "already dumped: %p, data=%p\n", (void*) value_seen, (void*) value_seen->struct_data);
89 return true;
90 }
91
92 if (!pw_super(mthis, self, fp, indent, tail)) {
93 return false;
94 }
95
96 _PwCompoundData* cdata = get_this_cdata(self);
97
98 _pw_print_indent(fp, indent + 4);
99 fprintf(fp, "Set refcount: %u (%s) at %p (cdata=%p)\n",
100 _pw_atomic_load(cdata->set_refcount_ptr),
101 (cdata->set_refcount_ptr == &cdata->set_refcount)? "this" : "foreign",
102 (void*) cdata->set_refcount_ptr,
103 (void*) cdata);
104 return true;
105}
106
107PwInterface_Basic _pw_compound_basic_interface = {
108 .create = { .func = compound_create },
109 .destroy = { .func = compound_destroy },
110 .clone = { .func = compound_clone },
111 .decref = { .func = compound_decref },
112 .dump = { .func = compound_dump }
113};
114
115/****************************************************************
116 * Join/split sets of compound values
117 */
118
119typedef struct {
120 PwValuePtr parent;
121 unsigned total_refcount; // total refcount of all children
122 unsigned internal_refcount; // number of references between children
123 _PwCompoundData* set_refcount_host;
124 bool have_refs_to_parent;
125} CircularityCheckerData;
126
127static void check_circularity(PwValuePtr value, _PwCompoundChain* tail, void* udata)
128/*
129 * Set `have_refs_to_parent` field in (CircularityCheckerData*) udata if value circularily refers to parent.
130 *
131 * If there's no circular references to parent, all other fields are valid.
132 */
133{
134 CircularityCheckerData* ccdata = (CircularityCheckerData*) udata;
135
136 if (value->struct_data == ccdata->parent->struct_data) {
137 ccdata->have_refs_to_parent = true;
138 return;
139 }
140 _PwCompoundData* cdata = _pw_get_struct_ptr(value, PwTypeId_Compound); // XXX optimize, CompoundData always follows StructData
141 if (cdata->set_refcount_ptr == &cdata->set_refcount) {
142 ccdata->set_refcount_host = cdata;
143 }
144
145 ccdata->total_refcount += _pw_atomic_load(&((_PwStructData*) value->struct_data)->refcount);
146 ccdata->internal_refcount++;
147
148 bool local_circularity = false;
149 for (_PwCompoundChain* prev = tail; prev; prev = prev->prev) {
150 auto struct_data = prev->value->struct_data;
151 if (struct_data == ccdata->parent->struct_data) {
152 ccdata->have_refs_to_parent = true;
153 return;
154 }
155 if (struct_data == value->struct_data) {
156 local_circularity = true;
157 ccdata->internal_refcount++;
158 }
159 }
160 if (local_circularity) {
161 return;
162 }
163
164 PwMethod_Basic_iter_children* meth_iter_children;
165 if (!pw_method(value->type_id, Basic, iter_children, &meth_iter_children)) {
166 return;
167 }
168 PwFunc_Basic_iter_children fn_iter_children = meth_iter_children->func;
169 if (_pw_likely(!fn_iter_children)) {
170 return;
171 }
172 // compound chain is to avoid infinite loops only; circular links between children are okay
173 _PwCompoundChain cc_link = {
174 .prev = tail,
175 .value = value
176 };
177 fn_iter_children(meth_iter_children, value, &cc_link, check_circularity, udata);
178}
179
180static void replace_set_refcount_ptr(PwValuePtr value, _PwCompoundChain* tail, void* set_refcount_ptr)
181{
182 _PwCompoundData* cdata = _pw_get_struct_ptr(value, PwTypeId_Compound); // XXX optimize, CompoundData always follows StructData
183 cdata->set_refcount_ptr = (atomic_uint*) set_refcount_ptr;
184
185 PwMethod_Basic_iter_children* meth_iter_children;
186 if (!pw_method(value->type_id, Basic, iter_children, &meth_iter_children)) {
187 return;
188 }
189 PwFunc_Basic_iter_children fn_iter_children = meth_iter_children->func;
190 if (_pw_likely(!fn_iter_children)) {
191 return;
192 }
193 _PwCompoundChain cc_link = {
194 .prev = tail,
195 .value = value
196 };
197 fn_iter_children(meth_iter_children, value, &cc_link, replace_set_refcount_ptr, set_refcount_ptr);
198}
199
200void _pw_compound_split(PwValuePtr parent, PwValuePtr child)
201{
202 // XXX optimize, CompoundData always follows StructData
203 _PwCompoundData* parent_cdata = _pw_get_struct_ptr(parent, PwTypeId_Compound);
204 _PwCompoundData* child_cdata = _pw_get_struct_ptr(child, PwTypeId_Compound);
205
206 if (!(parent_cdata && child_cdata)) {
207 return;
208 }
209
210 CircularityCheckerData ccdata = {
211 .parent = parent
212 };
213 check_circularity(child, nullptr, &ccdata);
214
215 if (ccdata.have_refs_to_parent) {
216 /*
217 * Cannot split if child circularly references to parent.
218 * If `child` is removed from `parent` and still refers to it
219 * (e.g. array that has an item referring to self),
220 * the parent will be gone only when the last reference to the entire set is gone.
221 */
222 return;
223 }
224 unsigned num_child_external_refs = ccdata.total_refcount - ccdata.internal_refcount;
225 if (num_child_external_refs == 0) {
226 // all references to child are held by parent, splitting does not make sense
227 return;
228 }
229 if (ccdata.set_refcount_host) {
230 /*
231 * set_refcount is hosted in child's subset ao we cannot change set_refcount_ptr
232 * because it would require replacing it for all parent values.
233 * We can't do this without back reference to parent, so do not.
234 */
235 return;
236 }
237
238 // decrement parent set refcount
239
240 if (_pw_atomic_sub(parent_cdata->set_refcount_ptr, num_child_external_refs) == 0) {
241 pw_panic("Parent %p must have references\n", parent);
242 }
243
244 // init child's set_refcount
245
246 _pw_atomic_store(&child_cdata->set_refcount, num_child_external_refs);
247
248 // replace set_refcount ptr for grandchildren
249
250 replace_set_refcount_ptr(child, nullptr, &child_cdata->set_refcount);
251}
252
253void _pw_compound_join(PwValuePtr parent, PwValuePtr child)
254{
255 // XXX optimize, CompoundData always follows StructData
256 _PwCompoundData* parent_cdata = _pw_get_struct_ptr(parent, PwTypeId_Compound);
257 _PwCompoundData* child_cdata = _pw_get_struct_ptr(child, PwTypeId_Compound);
258
259 if (!(parent_cdata && child_cdata)) {
260 return;
261 }
262 if (parent_cdata == child_cdata) {
263 // reference to self
264 } else if (parent_cdata->set_refcount_ptr == child_cdata->set_refcount_ptr) {
265 // already joined
266 } else {
267 // add child set refcount to parent
268
269 unsigned child_set_refcount = _pw_atomic_load(child_cdata->set_refcount_ptr);
270 _pw_atomic_add(parent_cdata->set_refcount_ptr, child_set_refcount);
271
272 // replace set_refcount ptr for child and grandchildren
273
274 replace_set_refcount_ptr(child, nullptr, parent_cdata->set_refcount_ptr);
275 }
276 // decrement set_refcount
277 _pw_atomic_sub(parent_cdata->set_refcount_ptr, 1);
278}