Line data Source code
1 : #include "fd_funk.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 1322751 : fake_rec(ulong key) : _key(key) {
25 1322751 : assert(_all.count(this) == 0);
26 1322751 : _all.insert(this);
27 1322751 : }
28 1322751 : ~fake_rec() {
29 1322751 : assert(_all.count(this) == 1);
30 1322751 : _all.erase(this);
31 1322751 : }
32 :
33 1322751 : static fake_rec * make_random() {
34 1322751 : auto * rec = new fake_rec(((ulong)lrand48())%MAX_CHILDREN);
35 1322751 : auto len = ((ulong)lrand48())%8UL;
36 1322751 : rec->_data.resize(len);
37 5947251 : for (ulong i = 0; i < len; ++i)
38 4624500 : rec->_data[i] = lrand48();
39 1322751 : return rec;
40 1322751 : }
41 :
42 1545780 : fd_funk_rec_key_t real_id() const {
43 1545780 : fd_funk_rec_key_t i;
44 1545780 : memset(&i, 0, sizeof(i));
45 1545780 : i.ul[0] = _key;
46 1545780 : return i;
47 1545780 : }
48 :
49 33861528 : ulong size() const {
50 33861528 : return _data.size()*sizeof(long);
51 33861528 : }
52 :
53 16302324 : const uchar* data() const {
54 16302324 : return (const uchar*)_data.data();
55 16302324 : }
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 1170216 : for (auto i : _recs) {
70 1170216 : delete i;
71 1170216 : }
72 240003 : }
73 :
74 2022783 : fd_funk_txn_xid_t real_id() const {
75 2022783 : fd_funk_txn_xid_t i;
76 2022783 : memset(&i, 0, sizeof(i));
77 2022783 : i.ul[0] = _key;
78 2022783 : return i;
79 2022783 : }
80 :
81 1459506 : bool insert(fake_rec* rec) {
82 1459506 : for (auto i : _recs)
83 15072126 : if( i->_key == rec->_key ) {
84 65871 : delete rec;
85 65871 : return false; /* Error */
86 65871 : }
87 1393635 : auto sz = _recs.size();
88 1393635 : _recs.resize(sz+1);
89 1393635 : _recs[sz] = rec;
90 1393635 : return true;
91 1459506 : }
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 81 : 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 1560000 : fake_txn * pick_unfrozen_txn() {
121 1560000 : fake_txn* list[MAX_TXNS];
122 1560000 : uint listlen = 0;
123 1560000 : for (auto i : _txns)
124 34015860 : if (i.second->_children.size() == 0)
125 17090100 : list[listlen++] = i.second;
126 1560000 : return list[((uint)lrand48())%listlen];
127 1560000 : }
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 1256880 : fake_rec * rec = NULL;
143 1322751 : do {
144 1322751 : rec = fake_rec::make_random();
145 : /* Prevent duplicate keys */
146 1322751 : } while (!txn->insert(rec));
147 :
148 1256880 : auto key = rec->real_id();
149 1256880 : fd_funk_rec_prepare_t prepare[1];
150 1256880 : fd_funk_rec_t * rec2 = fd_funk_rec_prepare(_real, get_real_txn(txn), &key, prepare, NULL);
151 1256880 : void * val = fd_funk_val_truncate(rec2, fd_funk_alloc( _real ), _wksp, 0UL, rec->size(), NULL);
152 1256880 : memcpy(val, rec->data(), rec->size());
153 1256880 : fd_funk_rec_publish( _real, prepare );
154 1256880 : assert(fd_funk_val_sz(rec2) == rec->size());
155 1256880 : }
156 :
157 300000 : void random_remove() {
158 300000 : fake_txn * txn = pick_unfrozen_txn();
159 300000 : auto& recs = txn->_recs;
160 300000 : fake_rec* list[MAX_CHILDREN];
161 300000 : uint listlen = 0;
162 300000 : for (auto i : recs)
163 2200485 : if (!i->_erased)
164 1899756 : list[listlen++] = i;
165 300000 : if (!listlen) return;
166 288900 : auto* rec = list[((uint)lrand48())%listlen];
167 :
168 288900 : auto key = rec->real_id();
169 288900 : assert(fd_funk_rec_remove(_real, get_real_txn(txn), &key, NULL) == FD_FUNK_SUCCESS);
170 :
171 288900 : rec->_erased = true;
172 288900 : rec->_data.clear();
173 288900 : }
174 :
175 240000 : void random_new_txn() {
176 240000 : if (_txns.size() == MAX_TXNS)
177 0 : return;
178 :
179 240000 : fake_txn* list[MAX_TXNS];
180 240000 : uint listlen = 0;
181 240000 : for (auto i : _txns)
182 3869550 : list[listlen++] = i.second;
183 240000 : auto * parent = list[((uint)lrand48())%listlen];
184 :
185 240000 : ulong key = ++_lastxid;
186 240000 : auto * txn = _txns[key] = new fake_txn(key);
187 :
188 240000 : txn->_parent = parent;
189 240000 : parent->_children[key] = txn;
190 :
191 240000 : auto xid = txn->real_id();
192 240000 : fd_funk_txn_prepare(_real, get_real_txn(parent), &xid);
193 240000 : }
194 :
195 210396 : void fake_cancel_family(fake_txn* txn) {
196 210396 : assert(txn->_key != ROOT_KEY);
197 358887 : while (!txn->_children.empty())
198 148491 : fake_cancel_family(txn->_children.begin()->second);
199 210396 : txn->_parent->_children.erase(txn->_key);
200 210396 : _txns.erase(txn->_key);
201 210396 : delete txn;
202 210396 : }
203 :
204 29526 : void fake_publish_to_parent(fake_txn* txn) {
205 : // Move records into parent
206 29526 : auto* parent = txn->_parent;
207 136755 : for (auto i : txn->_recs) {
208 136755 : uint p = 0;
209 4416702 : for (auto j : parent->_recs) {
210 4416702 : if( i->_key == j->_key ) {
211 86664 : delete j;
212 86664 : parent->_recs.erase(parent->_recs.begin()+p);
213 86664 : break;
214 86664 : }
215 4330038 : p++;
216 4330038 : }
217 136755 : parent->insert(i);
218 136755 : }
219 29526 : txn->_recs.clear();
220 :
221 : // Cancel siblings
222 85431 : for (;;) {
223 85431 : bool repeat = false;
224 85431 : for (auto i : parent->_children)
225 119310 : if (txn != i.second) {
226 55905 : fake_cancel_family(i.second);
227 55905 : repeat = true;
228 55905 : break;
229 55905 : }
230 85431 : if (!repeat) break;
231 85431 : }
232 29526 : assert(parent->_children.size() == 1 && parent->_children[txn->_key] == txn);
233 :
234 : // Move children up
235 29526 : parent->_children.clear();
236 44256 : for (auto i : txn->_children) {
237 44256 : auto* child = i.second;
238 44256 : child->_parent = parent;
239 44256 : parent->_children[child->_key] = child;
240 44256 : }
241 :
242 29526 : _txns.erase(txn->_key);
243 29526 : delete txn;
244 29526 : }
245 :
246 17526 : void fake_publish(fake_txn* txn) {
247 17526 : assert(txn->_key != ROOT_KEY);
248 17526 : if (txn->_parent->_key != ROOT_KEY)
249 11526 : fake_publish(txn->_parent);
250 17526 : assert(txn->_parent->_key == ROOT_KEY);
251 17526 : fake_publish_to_parent(txn);
252 17526 : }
253 :
254 0 : void random_publish() {
255 0 : fake_txn* list[MAX_TXNS];
256 0 : uint listlen = 0;
257 0 : for (auto i : _txns)
258 0 : if (i.second->_key != ROOT_KEY)
259 0 : list[listlen++] = i.second;
260 0 : if (!listlen) return;
261 0 : auto * txn = list[((uint)lrand48())%listlen];
262 0 :
263 0 : assert(fd_funk_txn_publish(_real, get_real_txn(txn)) > 0);
264 0 :
265 0 : // Simulate publication
266 0 : fake_publish(txn);
267 0 : }
268 :
269 0 : void random_publish_into_parent() {
270 0 : fake_txn* list[MAX_TXNS];
271 0 : uint listlen = 0;
272 0 : for (auto i : _txns)
273 0 : if (i.second->_key != ROOT_KEY)
274 0 : list[listlen++] = i.second;
275 0 : if (!listlen) {
276 0 : return;
277 0 : }
278 0 : auto * txn = list[((uint)lrand48())%listlen];
279 0 :
280 0 : fd_funk_txn_publish_into_parent(_real, get_real_txn(txn));
281 0 :
282 0 : // Simulate publication
283 0 : fake_publish_to_parent(txn);
284 0 : }
285 :
286 0 : void random_cancel() {
287 0 : fake_txn* list[MAX_TXNS];
288 0 : uint listlen = 0;
289 0 : for (auto i : _txns)
290 0 : if (i.second->_key != ROOT_KEY)
291 0 : list[listlen++] = i.second;
292 0 : if (!listlen) return;
293 0 : auto * txn = list[((uint)lrand48())%listlen];
294 0 :
295 0 : assert(fd_funk_txn_cancel(_real, get_real_txn(txn)) > 0);
296 0 :
297 0 : // Simulate cancel
298 0 : fake_cancel_family(txn);
299 0 : }
300 :
301 102003 : void verify() {
302 : #ifdef FD_FUNK_HANDHOLDING
303 : assert(fd_funk_verify(_real) == FD_FUNK_SUCCESS);
304 : #endif
305 :
306 1949829 : for (auto i : _txns) {
307 1949829 : assert(i.first == i.second->_key);
308 18806709 : for (auto j : i.second->_recs) {
309 18806709 : j->_touched = false;
310 18806709 : }
311 1949829 : }
312 :
313 102003 : fd_funk_all_iter_t iter[1];
314 18908712 : for( fd_funk_all_iter_new( _real, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
315 18806709 : fd_funk_rec_t const * rec = fd_funk_all_iter_ele_const( iter );
316 18806709 : auto const * xid = fd_funk_rec_xid( rec );
317 18806709 : auto i = _txns.find(xid->ul[0]);
318 :
319 18806709 : assert(i != _txns.end());
320 18806709 : auto const * key = fd_funk_rec_key( rec );
321 18806709 : auto& recs = i->second->_recs;
322 561845241 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
323 18806709 : assert(j != recs.end());
324 18806709 : auto * rec2 = *j;
325 18806709 : if (rec2->_erased) {
326 3761265 : assert(rec->flags & FD_FUNK_REC_FLAG_ERASE);
327 3761265 : assert(fd_funk_val_sz(rec) == 0);
328 15045444 : } else {
329 15045444 : assert(!(rec->flags & FD_FUNK_REC_FLAG_ERASE));
330 15045444 : assert(fd_funk_val_sz(rec) == rec2->size());
331 15045444 : assert(memcmp(fd_funk_val(rec, _wksp), rec2->data(), rec2->size()) == 0);
332 15045444 : }
333 :
334 18806709 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
335 18806709 : fd_funk_txn_t * txn = fd_funk_txn_query( xid, txn_map );
336 18806709 : if( !txn ) xid = fd_funk_last_publish( _real );
337 18806709 : fd_funk_rec_query_t query[1];
338 18806709 : auto* rec3 = fd_funk_rec_query_try_global(_real, xid, rec->pair.key, NULL, query);
339 18806709 : if( ( rec->flags & FD_FUNK_REC_FLAG_ERASE ) )
340 18806709 : assert(rec3 == NULL);
341 15045444 : else
342 18806709 : assert(rec == rec3);
343 18806709 : assert(!fd_funk_rec_query_test( query ));
344 :
345 18806709 : assert(!rec2->_touched);
346 18806709 : rec2->_touched = true;
347 18806709 : }
348 :
349 1949829 : for (auto i : _txns) {
350 18806709 : for (auto j : i.second->_recs) {
351 18806709 : assert(j->_touched || j->_erased);
352 18806709 : }
353 1949829 : }
354 :
355 1949829 : for (auto i : _txns) {
356 1949829 : auto * txn = i.second;
357 1949829 : assert(i.first == txn->_key);
358 1949829 : if (txn->_key == ROOT_KEY) {
359 102003 : assert(txn->_parent == NULL);
360 1847826 : } else {
361 1847826 : assert(txn->_parent->_children.find(txn->_key)->second == txn);
362 1847826 : }
363 1949829 : txn->_touched = false;
364 1949829 : }
365 :
366 102003 : {
367 : // Root transaction
368 102003 : auto * txn2 = _txns[ROOT_KEY];
369 102003 : assert(!txn2->_touched);
370 102003 : txn2->_touched = true;
371 :
372 102003 : auto& recs = txn2->_recs;
373 102003 : for( auto const * rec = fd_funk_txn_first_rec(_real, NULL);
374 102003 : rec;
375 102003 : rec = fd_funk_txn_next_rec(_real, rec) ) {
376 0 : auto const * key = fd_funk_rec_key( rec );
377 0 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
378 0 : assert(j != recs.end());
379 0 : }
380 102003 : }
381 :
382 102003 : fd_funk_txn_pool_t * txn_pool = fd_funk_txn_pool( _real );
383 :
384 102003 : fd_funk_txn_all_iter_t txn_iter[1];
385 1949829 : 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 ) ) {
386 1847826 : fd_funk_txn_t const * txn = fd_funk_txn_all_iter_ele_const( txn_iter );
387 :
388 1847826 : auto i = _txns.find(txn->xid.ul[0]);
389 1847826 : assert(i != _txns.end());
390 1847826 : auto * txn2 = i->second;
391 1847826 : assert(!txn2->_touched);
392 1847826 : txn2->_touched = true;
393 :
394 1847826 : auto * parent = fd_funk_txn_parent(txn, txn_pool);
395 1847826 : if (parent == NULL)
396 1847826 : assert(ROOT_KEY == txn2->_parent->_key);
397 1504497 : else
398 1847826 : assert(parent->xid.ul[0] == txn2->_parent->_key);
399 :
400 1847826 : auto& recs = txn2->_recs;
401 1847826 : for( auto const * rec = fd_funk_txn_first_rec(_real, txn);
402 10482315 : rec;
403 8634489 : rec = fd_funk_txn_next_rec(_real, rec) ) {
404 8634489 : auto const * key = fd_funk_rec_key( rec );
405 48779472 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
406 8634489 : assert(j != recs.end());
407 8634489 : }
408 1847826 : }
409 :
410 1949829 : for (auto i : _txns) {
411 : assert(i.second->_touched);
412 1949829 : }
413 102003 : }
414 : };
|
