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 : #ifdef FUNK_RECONNECT_TEST
109 : struct stat x;
110 : if( stat("/mnt/.fd/.gigantic/reconnect_test", &x) == 0) {
111 : void * shmem = fd_shmem_join( "reconnect_test", FD_SHMEM_JOIN_MODE_READ_WRITE, NULL, NULL, NULL, 1 ); /* logs details */
112 : FD_TEST( shmem != NULL );
113 : _wksp = fd_wksp_join( shmem );
114 : FD_TEST( _wksp != NULL );
115 : FD_TEST( fd_wksp_owner( _wksp ) == ULONG_MAX );
116 : ulong tag = FD_FUNK_MAGIC;
117 : fd_wksp_tag_query_info_t info;
118 : FD_TEST( fd_wksp_tag_query( _wksp, &tag, 1, &info, 1 ) > 0 );
119 : assert(info.tag == tag);
120 : FD_TEST( fd_funk_purify( (uchar*)shmem + info.gaddr_lo ) == FD_FUNK_SUCCESS );
121 : FD_TEST( fd_funk_join( _real, (uchar*)shmem + info.gaddr_lo ) );
122 : fd_funk_all_iter_t iter[1];
123 : for( fd_funk_all_iter_new( _real, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
124 : fd_funk_rec_t const * rec = fd_funk_all_iter_ele_const( iter );
125 : void * val = fd_funk_val( rec, _wksp );
126 : ulong sz = fd_funk_val_sz( rec );
127 : fake_rec * rec2 = new fake_rec( fd_funk_rec_key( rec )->ul[0] );
128 : rec2->_data.resize( sz/8UL );
129 : memcpy( rec2->_data.data(), val, sz );
130 : _txns[ROOT_KEY]->_recs.push_back( rec2 );
131 : }
132 :
133 : } else {
134 : FD_TEST( !fd_shmem_create( "reconnect_test", FD_SHMEM_GIGANTIC_PAGE_SZ, 1U, fd_shmem_cpu_idx( numa_idx ), 0600 ) );
135 : void * shmem = fd_shmem_join( "reconnect_test", FD_SHMEM_JOIN_MODE_READ_WRITE, NULL, NULL, NULL, 1 ); /* logs details */
136 : void * wkspmem = fd_wksp_new( shmem, "reconect_test", 0U, 1024, FD_SHMEM_GIGANTIC_PAGE_SZ ); /* logs details */
137 : _wksp = fd_wksp_join( wkspmem );
138 : void * mem = fd_wksp_alloc_laddr( _wksp, fd_funk_align(), fd_funk_footprint( txn_max, rec_max ), FD_FUNK_MAGIC );
139 : FD_TEST( fd_funk_join( _real, fd_funk_new( mem, 1, 1234U, txn_max, rec_max ) ) );
140 : }
141 : #else
142 3 : _wksp = fd_wksp_new_anonymous( FD_SHMEM_GIGANTIC_PAGE_SZ, 1U, fd_shmem_cpu_idx( numa_idx ), "wksp", 0UL );
143 3 : void * mem = fd_wksp_alloc_laddr( _wksp, fd_funk_align(), fd_funk_footprint( txn_max, rec_max ), FD_FUNK_MAGIC );
144 3 : FD_TEST( fd_funk_join( _real, fd_funk_new( mem, 1, 1234U, txn_max, rec_max ) ) );
145 3 : #endif
146 3 : }
147 3 : ~fake_funk() {
148 3 : for (auto i : _txns)
149 81 : delete i.second;
150 3 : for( auto i : fake_rec::_all )
151 0 : FD_LOG_NOTICE(( "leaked record 0x%lx!", (ulong)i ));
152 :
153 3 : }
154 :
155 1560000 : fake_txn * pick_unfrozen_txn() {
156 1560000 : fake_txn* list[MAX_TXNS];
157 1560000 : uint listlen = 0;
158 1560000 : for (auto i : _txns)
159 34015860 : if (i.second->_children.size() == 0)
160 17090100 : list[listlen++] = i.second;
161 1560000 : return list[((uint)lrand48())%listlen];
162 1560000 : }
163 :
164 1809780 : fd_funk_txn_t * get_real_txn(fake_txn * txn) {
165 1809780 : if (txn->_key == ROOT_KEY)
166 26997 : return NULL;
167 1782783 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
168 1782783 : auto xid = txn->real_id();
169 1782783 : return fd_funk_txn_query(&xid, txn_map);
170 1809780 : }
171 :
172 1260000 : void random_insert() {
173 1260000 : fake_txn * txn = pick_unfrozen_txn();
174 1260000 : if( txn->_recs.size() == MAX_CHILDREN ) return;
175 1256880 : fake_rec * rec = NULL;
176 1322751 : do {
177 1322751 : rec = fake_rec::make_random();
178 : /* Prevent duplicate keys */
179 1322751 : } while (!txn->insert(rec));
180 :
181 1256880 : fd_funk_txn_t * txn2 = get_real_txn(txn);
182 1256880 : auto key = rec->real_id();
183 1256880 : fd_funk_rec_prepare_t prepare[1];
184 1256880 : fd_funk_rec_t * rec2 = fd_funk_rec_prepare(_real, txn2, &key, prepare, NULL);
185 1256880 : void * val = fd_funk_val_truncate(rec2, fd_funk_alloc( _real ), _wksp, 0UL, rec->size(), NULL);
186 1256880 : memcpy(val, rec->data(), rec->size());
187 1256880 : fd_funk_rec_publish( _real, prepare );
188 1256880 : assert(fd_funk_val_sz(rec2) == rec->size());
189 1256880 : }
190 :
191 300000 : void random_remove() {
192 300000 : fake_txn * txn = pick_unfrozen_txn();
193 300000 : auto& recs = txn->_recs;
194 300000 : fake_rec* list[MAX_CHILDREN];
195 300000 : uint listlen = 0;
196 300000 : for (auto i : recs)
197 2200485 : if (!i->_erased)
198 1899756 : list[listlen++] = i;
199 300000 : if (!listlen) return;
200 288900 : auto* rec = list[((uint)lrand48())%listlen];
201 :
202 288900 : fd_funk_txn_t * txn2 = get_real_txn(txn);
203 288900 : auto key = rec->real_id();
204 288900 : assert(fd_funk_rec_remove(_real, txn2, &key, NULL) == FD_FUNK_SUCCESS);
205 :
206 288900 : rec->_erased = true;
207 288900 : rec->_data.clear();
208 288900 : }
209 :
210 240000 : void random_new_txn() {
211 240000 : if (_txns.size() == MAX_TXNS)
212 0 : return;
213 :
214 240000 : fake_txn* list[MAX_TXNS];
215 240000 : uint listlen = 0;
216 240000 : for (auto i : _txns)
217 3869550 : list[listlen++] = i.second;
218 240000 : auto * parent = list[((uint)lrand48())%listlen];
219 :
220 240000 : ulong key = ++_lastxid;
221 240000 : auto * txn = _txns[key] = new fake_txn(key);
222 :
223 240000 : txn->_parent = parent;
224 240000 : parent->_children[key] = txn;
225 :
226 240000 : fd_funk_txn_t * parent2 = get_real_txn(parent);
227 240000 : auto xid = txn->real_id();
228 240000 : assert(fd_funk_txn_prepare(_real, parent2, &xid, 1) != NULL);
229 240000 : }
230 :
231 210396 : void fake_cancel_family(fake_txn* txn) {
232 210396 : assert(txn->_key != ROOT_KEY);
233 358887 : while (!txn->_children.empty())
234 148491 : fake_cancel_family(txn->_children.begin()->second);
235 210396 : txn->_parent->_children.erase(txn->_key);
236 210396 : _txns.erase(txn->_key);
237 210396 : delete txn;
238 210396 : }
239 :
240 29526 : void fake_publish_to_parent(fake_txn* txn) {
241 : // Move records into parent
242 29526 : auto* parent = txn->_parent;
243 136755 : for (auto i : txn->_recs) {
244 136755 : uint p = 0;
245 4416702 : for (auto j : parent->_recs) {
246 4416702 : if( i->_key == j->_key ) {
247 86664 : delete j;
248 86664 : parent->_recs.erase(parent->_recs.begin()+p);
249 86664 : break;
250 86664 : }
251 4330038 : p++;
252 4330038 : }
253 136755 : parent->insert(i);
254 136755 : }
255 29526 : txn->_recs.clear();
256 :
257 : // Cancel siblings
258 85431 : for (;;) {
259 85431 : bool repeat = false;
260 85431 : for (auto i : parent->_children)
261 119310 : if (txn != i.second) {
262 55905 : fake_cancel_family(i.second);
263 55905 : repeat = true;
264 55905 : break;
265 55905 : }
266 85431 : if (!repeat) break;
267 85431 : }
268 29526 : assert(parent->_children.size() == 1 && parent->_children[txn->_key] == txn);
269 :
270 : // Move children up
271 29526 : parent->_children.clear();
272 44256 : for (auto i : txn->_children) {
273 44256 : auto* child = i.second;
274 44256 : child->_parent = parent;
275 44256 : parent->_children[child->_key] = child;
276 44256 : }
277 :
278 29526 : _txns.erase(txn->_key);
279 29526 : delete txn;
280 29526 : }
281 :
282 17526 : void fake_publish(fake_txn* txn) {
283 17526 : assert(txn->_key != ROOT_KEY);
284 17526 : if (txn->_parent->_key != ROOT_KEY)
285 11526 : fake_publish(txn->_parent);
286 17526 : assert(txn->_parent->_key == ROOT_KEY);
287 17526 : fake_publish_to_parent(txn);
288 17526 : }
289 :
290 0 : void random_publish() {
291 0 : fake_txn* list[MAX_TXNS];
292 0 : uint listlen = 0;
293 0 : for (auto i : _txns)
294 0 : if (i.second->_key != ROOT_KEY)
295 0 : list[listlen++] = i.second;
296 0 : if (!listlen) return;
297 0 : auto * txn = list[((uint)lrand48())%listlen];
298 0 :
299 0 : fd_funk_txn_t * txn2 = get_real_txn(txn);
300 0 : assert(fd_funk_txn_publish(_real, txn2, 1) > 0);
301 0 :
302 0 : // Simulate publication
303 0 : fake_publish(txn);
304 0 : }
305 :
306 12000 : void random_publish_into_parent() {
307 12000 : fake_txn* list[MAX_TXNS];
308 12000 : uint listlen = 0;
309 12000 : for (auto i : _txns)
310 233541 : if (i.second->_key != ROOT_KEY)
311 221541 : list[listlen++] = i.second;
312 12000 : if (!listlen) {
313 0 : return;
314 0 : }
315 12000 : auto * txn = list[((uint)lrand48())%listlen];
316 :
317 12000 : fd_funk_txn_t * txn2 = get_real_txn(txn);
318 12000 : assert(fd_funk_txn_publish_into_parent(_real, txn2, 1) == FD_FUNK_SUCCESS);
319 :
320 : // Simulate publication
321 12000 : fake_publish_to_parent(txn);
322 12000 : }
323 :
324 0 : void random_cancel() {
325 0 : fake_txn* list[MAX_TXNS];
326 0 : uint listlen = 0;
327 0 : for (auto i : _txns)
328 0 : if (i.second->_key != ROOT_KEY)
329 0 : list[listlen++] = i.second;
330 0 : if (!listlen) return;
331 0 : auto * txn = list[((uint)lrand48())%listlen];
332 0 :
333 0 : fd_funk_txn_t * txn2 = get_real_txn(txn);
334 0 : assert(fd_funk_txn_cancel(_real, txn2, 1) > 0);
335 0 :
336 0 : // Simulate cancel
337 0 : fake_cancel_family(txn);
338 0 : }
339 :
340 102003 : void verify() {
341 : #ifdef FD_FUNK_HANDHOLDING
342 : assert(fd_funk_verify(_real) == FD_FUNK_SUCCESS);
343 : #endif
344 :
345 1949829 : for (auto i : _txns) {
346 1949829 : assert(i.first == i.second->_key);
347 18806709 : for (auto j : i.second->_recs) {
348 18806709 : j->_touched = false;
349 18806709 : }
350 1949829 : }
351 :
352 102003 : fd_funk_all_iter_t iter[1];
353 18908712 : for( fd_funk_all_iter_new( _real, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
354 18806709 : fd_funk_rec_t const * rec = fd_funk_all_iter_ele_const( iter );
355 18806709 : auto const * xid = fd_funk_rec_xid( rec );
356 18806709 : auto i = _txns.find(xid->ul[0]);
357 :
358 18806709 : assert(i != _txns.end());
359 18806709 : auto const * key = fd_funk_rec_key( rec );
360 18806709 : auto& recs = i->second->_recs;
361 561845241 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
362 18806709 : assert(j != recs.end());
363 18806709 : auto * rec2 = *j;
364 18806709 : if (rec2->_erased) {
365 3761265 : assert(rec->flags & FD_FUNK_REC_FLAG_ERASE);
366 3761265 : assert(fd_funk_val_sz(rec) == 0);
367 15045444 : } else {
368 15045444 : assert(!(rec->flags & FD_FUNK_REC_FLAG_ERASE));
369 15045444 : assert(fd_funk_val_sz(rec) == rec2->size());
370 15045444 : assert(memcmp(fd_funk_val(rec, _wksp), rec2->data(), rec2->size()) == 0);
371 15045444 : }
372 :
373 18806709 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
374 18806709 : fd_funk_txn_t * txn = fd_funk_txn_query( xid, txn_map );
375 18806709 : fd_funk_rec_query_t query[1];
376 18806709 : auto* rec3 = fd_funk_rec_query_try_global(_real, txn, rec->pair.key, NULL, query);
377 18806709 : if( ( rec->flags & FD_FUNK_REC_FLAG_ERASE ) )
378 18806709 : assert(rec3 == NULL);
379 15045444 : else
380 18806709 : assert(rec == rec3);
381 18806709 : assert(!fd_funk_rec_query_test( query ));
382 :
383 18806709 : assert(!rec2->_touched);
384 18806709 : rec2->_touched = true;
385 18806709 : }
386 :
387 1949829 : for (auto i : _txns) {
388 18806709 : for (auto j : i.second->_recs) {
389 18806709 : assert(j->_touched || j->_erased);
390 18806709 : }
391 1949829 : }
392 :
393 1949829 : for (auto i : _txns) {
394 1949829 : auto * txn = i.second;
395 1949829 : assert(i.first == txn->_key);
396 1949829 : if (txn->_key == ROOT_KEY) {
397 102003 : assert(txn->_parent == NULL);
398 1847826 : } else {
399 1847826 : assert(txn->_parent->_children.find(txn->_key)->second == txn);
400 1847826 : }
401 1949829 : txn->_touched = false;
402 1949829 : }
403 :
404 102003 : {
405 : // Root transaction
406 102003 : auto * txn2 = _txns[ROOT_KEY];
407 102003 : assert(!txn2->_touched);
408 102003 : txn2->_touched = true;
409 :
410 102003 : auto& recs = txn2->_recs;
411 102003 : for( auto const * rec = fd_funk_txn_first_rec(_real, NULL);
412 102003 : rec;
413 102003 : rec = fd_funk_txn_next_rec(_real, rec) ) {
414 0 : auto const * key = fd_funk_rec_key( rec );
415 0 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
416 0 : assert(j != recs.end());
417 0 : }
418 102003 : }
419 :
420 102003 : fd_funk_txn_pool_t * txn_pool = fd_funk_txn_pool( _real );
421 :
422 102003 : fd_funk_txn_all_iter_t txn_iter[1];
423 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 ) ) {
424 1847826 : fd_funk_txn_t const * txn = fd_funk_txn_all_iter_ele_const( txn_iter );
425 :
426 1847826 : auto i = _txns.find(txn->xid.ul[0]);
427 1847826 : assert(i != _txns.end());
428 1847826 : auto * txn2 = i->second;
429 1847826 : assert(!txn2->_touched);
430 1847826 : txn2->_touched = true;
431 :
432 1847826 : auto * parent = fd_funk_txn_parent(txn, txn_pool);
433 1847826 : if (parent == NULL)
434 1847826 : assert(ROOT_KEY == txn2->_parent->_key);
435 1504497 : else
436 1847826 : assert(parent->xid.ul[0] == txn2->_parent->_key);
437 :
438 1847826 : auto& recs = txn2->_recs;
439 1847826 : for( auto const * rec = fd_funk_txn_first_rec(_real, txn);
440 10482315 : rec;
441 8634489 : rec = fd_funk_txn_next_rec(_real, rec) ) {
442 8634489 : auto const * key = fd_funk_rec_key( rec );
443 48779472 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
444 8634489 : assert(j != recs.end());
445 8634489 : }
446 1847826 : }
447 :
448 1949829 : for (auto i : _txns) {
449 : assert(i.second->_touched);
450 1949829 : }
451 102003 : }
452 : };
|
