Line data Source code
1 : #include "fd_funk_private.h"
2 : #include <map>
3 : #include <vector>
4 : #include <set>
5 : #include <algorithm>
6 : #include <stdlib.h>
7 : #include <assert.h>
8 : #include <unistd.h>
9 : #include <sys/stat.h>
10 :
11 : static const ulong ROOT_KEY = ULONG_MAX;
12 : static const ulong MAX_TXNS = 100;
13 : static const ulong MAX_CHILDREN = 100;
14 : static const uint MAX_PARTS = 8;
15 :
16 : struct fake_rec {
17 : ulong _key;
18 : std::vector<long> _data;
19 : bool _erased = false;
20 : bool _touched = false;
21 : static std::set<fake_rec*> _all;
22 :
23 : fake_rec() = delete;
24 1323993 : fake_rec(ulong key) : _key(key) {
25 1323993 : assert(_all.count(this) == 0);
26 1323993 : _all.insert(this);
27 1323993 : }
28 1323993 : ~fake_rec() {
29 1323993 : assert(_all.count(this) == 1);
30 1323993 : _all.erase(this);
31 1323993 : }
32 :
33 1323993 : static fake_rec * make_random() {
34 1323993 : auto * rec = new fake_rec(((ulong)lrand48())%MAX_CHILDREN);
35 1323993 : auto len = ((ulong)lrand48())%8UL;
36 1323993 : rec->_data.resize(len);
37 5944593 : for (ulong i = 0; i < len; ++i)
38 4620600 : rec->_data[i] = lrand48();
39 1323993 : return rec;
40 1323993 : }
41 :
42 1257840 : fd_funk_rec_key_t real_id() const {
43 1257840 : fd_funk_rec_key_t i;
44 1257840 : memset(&i, 0, sizeof(i));
45 1257840 : i.ul[0] = _key;
46 1257840 : return i;
47 1257840 : }
48 :
49 31231272 : ulong size() const {
50 31231272 : return _data.size()*sizeof(long);
51 31231272 : }
52 :
53 14986716 : const uchar* data() const {
54 14986716 : return (const uchar*)_data.data();
55 14986716 : }
56 : };
57 :
58 : std::set<fake_rec*> fake_rec::_all;
59 :
60 : struct fake_txn {
61 : ulong _key;
62 : std::vector<fake_rec*> _recs;
63 : std::map<ulong,fake_txn*> _children;
64 : fake_txn * _parent = NULL;
65 : bool _touched = false;
66 :
67 240003 : fake_txn(ulong key) : _key(key) { }
68 240003 : ~fake_txn() {
69 1172814 : for (auto i : _recs) {
70 1172814 : delete i;
71 1172814 : }
72 240003 : }
73 :
74 1735089 : fd_funk_txn_xid_t real_id() const {
75 1735089 : fd_funk_txn_xid_t i;
76 1735089 : memset(&i, 0, sizeof(i));
77 1735089 : i.ul[0] = _key;
78 1735089 : return i;
79 1735089 : }
80 :
81 1458096 : bool insert(fake_rec* rec) {
82 1458096 : for (auto i : _recs)
83 14923956 : if( i->_key == rec->_key ) {
84 66153 : delete rec;
85 66153 : return false; /* Error */
86 66153 : }
87 1391943 : auto sz = _recs.size();
88 1391943 : _recs.resize(sz+1);
89 1391943 : _recs[sz] = rec;
90 1391943 : return true;
91 1458096 : }
92 : };
93 :
94 : struct fake_funk {
95 : fd_wksp_t * _wksp;
96 : fd_funk_t _real[1];
97 : std::map<ulong,fake_txn*> _txns;
98 : ulong _lastxid = 0;
99 :
100 3 : fake_funk(int * argc, char *** argv) {
101 3 : fd_boot( argc, argv );
102 :
103 3 : ulong txn_max = 128;
104 3 : uint rec_max = 1<<16;
105 3 : ulong numa_idx = fd_shmem_numa_idx( 0 );
106 3 : _txns[ROOT_KEY] = new fake_txn(ROOT_KEY);
107 :
108 3 : _wksp = fd_wksp_new_anonymous( FD_SHMEM_GIGANTIC_PAGE_SZ, 1U, fd_shmem_cpu_idx( numa_idx ), "wksp", 0UL );
109 3 : void * mem = fd_wksp_alloc_laddr( _wksp, fd_funk_align(), fd_funk_footprint( txn_max, rec_max ), FD_FUNK_MAGIC );
110 3 : FD_TEST( fd_funk_join( _real, fd_funk_new( mem, 1, 1234U, txn_max, rec_max ) ) );
111 3 : }
112 3 : ~fake_funk() {
113 3 : for (auto i : _txns)
114 78 : delete i.second;
115 3 : for( auto i : fake_rec::_all )
116 0 : FD_LOG_NOTICE(( "leaked record 0x%lx!", (ulong)i ));
117 :
118 3 : }
119 :
120 1260000 : fake_txn * pick_unfrozen_txn() {
121 1260000 : fake_txn* list[MAX_TXNS];
122 1260000 : uint listlen = 0;
123 1260000 : for (auto i : _txns)
124 26939670 : if (i.second->_children.size() == 0)
125 13515900 : list[listlen++] = i.second;
126 1260000 : return list[((uint)lrand48())%listlen];
127 1260000 : }
128 :
129 0 : fd_funk_txn_xid_t const * get_real_txn(fake_txn * txn) {
130 0 : if (txn->_key == ROOT_KEY)
131 0 : return fd_funk_last_publish( _real );
132 0 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
133 0 : auto xid = txn->real_id();
134 0 : fd_funk_txn_t * rtxn = fd_funk_txn_query(&xid, txn_map);
135 0 : if( !rtxn ) return fd_funk_last_publish( _real );
136 0 : return &rtxn->xid;
137 0 : }
138 :
139 1260000 : void random_insert() {
140 1260000 : fake_txn * txn = pick_unfrozen_txn();
141 1260000 : if( txn->_recs.size() == MAX_CHILDREN ) return;
142 1257840 : fake_rec * rec = NULL;
143 1323993 : do {
144 1323993 : rec = fake_rec::make_random();
145 : /* Prevent duplicate keys */
146 1323993 : } while (!txn->insert(rec));
147 :
148 1257840 : auto key = rec->real_id();
149 1257840 : fd_funk_rec_prepare_t prepare[1];
150 1257840 : fd_funk_rec_t * rec2 = fd_funk_rec_prepare(_real, get_real_txn(txn), &key, prepare, NULL);
151 1257840 : void * val = fd_funk_val_truncate(rec2, fd_funk_alloc( _real ), _wksp, 0UL, rec->size(), NULL);
152 1257840 : memcpy(val, rec->data(), rec->size());
153 1257840 : fd_funk_rec_publish( _real, prepare );
154 1257840 : assert(fd_funk_val_sz(rec2) == rec->size());
155 1257840 : }
156 :
157 240000 : void random_new_txn() {
158 240000 : if (_txns.size() == MAX_TXNS)
159 0 : return;
160 :
161 240000 : fake_txn* list[MAX_TXNS];
162 240000 : uint listlen = 0;
163 240000 : for (auto i : _txns)
164 3840810 : list[listlen++] = i.second;
165 240000 : auto * parent = list[((uint)lrand48())%listlen];
166 :
167 240000 : ulong key = ++_lastxid;
168 240000 : auto * txn = _txns[key] = new fake_txn(key);
169 :
170 240000 : txn->_parent = parent;
171 240000 : parent->_children[key] = txn;
172 :
173 240000 : auto xid = txn->real_id();
174 240000 : fd_funk_txn_prepare(_real, get_real_txn(parent), &xid);
175 240000 : }
176 :
177 210165 : void fake_cancel_family(fake_txn* txn) {
178 210165 : assert(txn->_key != ROOT_KEY);
179 357576 : while (!txn->_children.empty())
180 147411 : fake_cancel_family(txn->_children.begin()->second);
181 210165 : txn->_parent->_children.erase(txn->_key);
182 210165 : _txns.erase(txn->_key);
183 210165 : delete txn;
184 210165 : }
185 :
186 29760 : void fake_publish_to_parent(fake_txn* txn) {
187 : // Move records into parent
188 29760 : auto* parent = txn->_parent;
189 134103 : for (auto i : txn->_recs) {
190 134103 : uint p = 0;
191 4352475 : for (auto j : parent->_recs) {
192 4352475 : if( i->_key == j->_key ) {
193 85026 : delete j;
194 85026 : parent->_recs.erase(parent->_recs.begin()+p);
195 85026 : break;
196 85026 : }
197 4267449 : p++;
198 4267449 : }
199 134103 : parent->insert(i);
200 134103 : }
201 29760 : txn->_recs.clear();
202 :
203 : // Cancel siblings
204 86514 : for (;;) {
205 86514 : bool repeat = false;
206 86514 : for (auto i : parent->_children)
207 120783 : if (txn != i.second) {
208 56754 : fake_cancel_family(i.second);
209 56754 : repeat = true;
210 56754 : break;
211 56754 : }
212 86514 : if (!repeat) break;
213 86514 : }
214 29760 : assert(parent->_children.size() == 1 && parent->_children[txn->_key] == txn);
215 :
216 : // Move children up
217 29760 : parent->_children.clear();
218 45882 : for (auto i : txn->_children) {
219 45882 : auto* child = i.second;
220 45882 : child->_parent = parent;
221 45882 : parent->_children[child->_key] = child;
222 45882 : }
223 :
224 29760 : _txns.erase(txn->_key);
225 29760 : delete txn;
226 29760 : }
227 :
228 17760 : void fake_publish(fake_txn* txn) {
229 17760 : assert(txn->_key != ROOT_KEY);
230 17760 : if (txn->_parent->_key != ROOT_KEY)
231 11760 : fake_publish(txn->_parent);
232 17760 : assert(txn->_parent->_key == ROOT_KEY);
233 17760 : fake_publish_to_parent(txn);
234 17760 : }
235 :
236 0 : void random_publish() {
237 0 : fake_txn* list[MAX_TXNS];
238 0 : uint listlen = 0;
239 0 : for (auto i : _txns)
240 0 : if (i.second->_key != ROOT_KEY)
241 0 : list[listlen++] = i.second;
242 0 : if (!listlen) return;
243 0 : auto * txn = list[((uint)lrand48())%listlen];
244 0 :
245 0 : assert(fd_funk_txn_publish(_real, get_real_txn(txn)) > 0);
246 0 :
247 0 : // Simulate publication
248 0 : fake_publish(txn);
249 0 : }
250 :
251 0 : void random_publish_into_parent() {
252 0 : fake_txn* list[MAX_TXNS];
253 0 : uint listlen = 0;
254 0 : for (auto i : _txns)
255 0 : if (i.second->_key != ROOT_KEY)
256 0 : list[listlen++] = i.second;
257 0 : if (!listlen) {
258 0 : return;
259 0 : }
260 0 : auto * txn = list[((uint)lrand48())%listlen];
261 0 :
262 0 : fd_funk_txn_publish_into_parent(_real, get_real_txn(txn));
263 0 :
264 0 : // Simulate publication
265 0 : fake_publish_to_parent(txn);
266 0 : }
267 :
268 0 : void random_cancel() {
269 0 : fake_txn* list[MAX_TXNS];
270 0 : uint listlen = 0;
271 0 : for (auto i : _txns)
272 0 : if (i.second->_key != ROOT_KEY)
273 0 : list[listlen++] = i.second;
274 0 : if (!listlen) return;
275 0 : auto * txn = list[((uint)lrand48())%listlen];
276 0 :
277 0 : assert(fd_funk_txn_cancel(_real, get_real_txn(txn)) > 0);
278 0 :
279 0 : // Simulate cancel
280 0 : fake_cancel_family(txn);
281 0 : }
282 :
283 0 : void verify() {
284 0 : #ifdef FD_FUNK_HANDHOLDING
285 0 : assert(fd_funk_verify(_real) == FD_FUNK_SUCCESS);
286 0 : #endif
287 0 :
288 0 : for (auto i : _txns) {
289 0 : assert(i.first == i.second->_key);
290 0 : for (auto j : i.second->_recs) {
291 0 : j->_touched = false;
292 0 : }
293 0 : }
294 0 :
295 0 : fd_funk_all_iter_t iter[1];
296 0 : for( fd_funk_all_iter_new( _real, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
297 0 : fd_funk_rec_t const * rec = fd_funk_all_iter_ele_const( iter );
298 0 : auto const * xid = fd_funk_rec_xid( rec );
299 0 : auto i = _txns.find(xid->ul[0]);
300 0 :
301 0 : assert(i != _txns.end());
302 0 : auto const * key = fd_funk_rec_key( rec );
303 0 : auto& recs = i->second->_recs;
304 426337743 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
305 0 : assert(j != recs.end());
306 0 : auto * rec2 = *j;
307 0 : assert(fd_funk_val_sz(rec) == rec2->size());
308 0 : assert(memcmp(fd_funk_val(rec, _wksp), rec2->data(), rec2->size()) == 0);
309 0 :
310 0 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
311 0 : fd_funk_txn_t * txn = fd_funk_txn_query( xid, txn_map );
312 0 : if( !txn ) xid = fd_funk_last_publish( _real );
313 0 : fd_funk_rec_query_t query[1];
314 0 : auto* rec3 = fd_funk_rec_query_try_global(_real, xid, rec->pair.key, NULL, query);
315 0 : assert(rec == rec3);
316 0 : assert(!fd_funk_rec_query_test( query ));
317 0 :
318 0 : assert(!rec2->_touched);
319 0 : rec2->_touched = true;
320 0 : }
321 0 :
322 0 : for (auto i : _txns) {
323 0 : for (auto j : i.second->_recs) {
324 0 : assert(j->_touched || j->_erased);
325 0 : }
326 0 : }
327 0 :
328 0 : for (auto i : _txns) {
329 0 : auto * txn = i.second;
330 0 : assert(i.first == txn->_key);
331 0 : if (txn->_key == ROOT_KEY) {
332 0 : assert(txn->_parent == NULL);
333 0 : } else {
334 0 : assert(txn->_parent->_children.find(txn->_key)->second == txn);
335 0 : }
336 0 : txn->_touched = false;
337 0 : }
338 0 :
339 0 : {
340 0 : // Root transaction
341 0 : auto * txn2 = _txns[ROOT_KEY];
342 0 : assert(!txn2->_touched);
343 0 : txn2->_touched = true;
344 0 :
345 0 : auto& recs = txn2->_recs;
346 0 : for( auto const * rec = fd_funk_txn_first_rec(_real, NULL);
347 0 : rec;
348 0 : rec = fd_funk_txn_next_rec(_real, rec) ) {
349 0 : auto const * key = fd_funk_rec_key( rec );
350 0 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
351 0 : assert(j != recs.end());
352 0 : }
353 0 : }
354 0 :
355 0 : fd_funk_txn_pool_t * txn_pool = fd_funk_txn_pool( _real );
356 0 :
357 0 : fd_funk_txn_all_iter_t txn_iter[1];
358 0 : for( fd_funk_txn_all_iter_new( _real, txn_iter ); !fd_funk_txn_all_iter_done( txn_iter ); fd_funk_txn_all_iter_next( txn_iter ) ) {
359 0 : fd_funk_txn_t const * txn = fd_funk_txn_all_iter_ele_const( txn_iter );
360 0 :
361 0 : auto i = _txns.find(txn->xid.ul[0]);
362 0 : assert(i != _txns.end());
363 0 : auto * txn2 = i->second;
364 0 : assert(!txn2->_touched);
365 0 : txn2->_touched = true;
366 0 :
367 0 : auto * parent = fd_funk_txn_parent(txn, txn_pool);
368 0 : if (parent == NULL)
369 0 : assert(ROOT_KEY == txn2->_parent->_key);
370 0 : else
371 0 : assert(parent->xid.ul[0] == txn2->_parent->_key);
372 0 :
373 0 : auto& recs = txn2->_recs;
374 0 : for( auto const * rec = fd_funk_txn_first_rec(_real, txn);
375 0 : rec;
376 0 : rec = fd_funk_txn_next_rec(_real, rec) ) {
377 0 : auto const * key = fd_funk_rec_key( rec );
378 33762030 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
379 0 : assert(j != recs.end());
380 0 : }
381 0 : }
382 0 :
383 0 : for (auto i : _txns) {
384 0 : assert(i.second->_touched);
385 0 : }
386 0 : }
387 : };
|
