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 long ROOT_KEY = 0;
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 1324362 : fake_rec(ulong key) : _key(key) {
25 1324362 : assert(_all.count(this) == 0);
26 1324362 : _all.insert(this);
27 1324362 : }
28 1324362 : ~fake_rec() {
29 1324362 : assert(_all.count(this) == 1);
30 1324362 : _all.erase(this);
31 1324362 : }
32 :
33 1324362 : static fake_rec * make_random() {
34 1324362 : auto * rec = new fake_rec(((ulong)lrand48())%MAX_CHILDREN);
35 1324362 : auto len = ((ulong)lrand48())%8UL;
36 1324362 : rec->_data.resize(len);
37 5948328 : for (ulong i = 0; i < len; ++i)
38 4623966 : rec->_data[i] = lrand48();
39 1324362 : return rec;
40 1324362 : }
41 :
42 1545966 : fd_funk_rec_key_t real_id() const {
43 1545966 : fd_funk_rec_key_t i;
44 1545966 : memset(&i, 0, sizeof(i));
45 1545966 : i.ul[0] = _key;
46 1545966 : return i;
47 1545966 : }
48 :
49 33917163 : ulong size() const {
50 33917163 : return _data.size()*sizeof(long);
51 33917163 : }
52 :
53 16329843 : const uchar* data() const {
54 16329843 : return (const uchar*)_data.data();
55 16329843 : }
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 1171947 : for (auto i : _recs) {
70 1171947 : delete i;
71 1171947 : }
72 240003 : }
73 :
74 2023092 : fd_funk_txn_xid_t real_id() const {
75 2023092 : fd_funk_txn_xid_t i;
76 2023092 : memset(&i, 0, sizeof(i));
77 2023092 : i.ul[0] = _key;
78 2023092 : return i;
79 2023092 : }
80 :
81 1459113 : bool insert(fake_rec* rec) {
82 1459113 : for (auto i : _recs)
83 15016125 : if( i->_key == rec->_key ) {
84 66885 : delete rec;
85 66885 : return false; /* Error */
86 66885 : }
87 1392228 : auto sz = _recs.size();
88 1392228 : _recs.resize(sz+1);
89 1392228 : _recs[sz] = rec;
90 1392228 : return true;
91 1459113 : }
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 42 : 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 33998520 : if (i.second->_children.size() == 0)
160 17102070 : list[listlen++] = i.second;
161 1560000 : return list[((uint)lrand48())%listlen];
162 1560000 : }
163 :
164 1809966 : fd_funk_txn_t * get_real_txn(fake_txn * txn) {
165 1809966 : if (txn->_key == ROOT_KEY)
166 26874 : return NULL;
167 1783092 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
168 1783092 : auto xid = txn->real_id();
169 1783092 : return fd_funk_txn_query(&xid, txn_map);
170 1809966 : }
171 :
172 1260000 : void random_insert() {
173 1260000 : fake_txn * txn = pick_unfrozen_txn();
174 1260000 : if( txn->_recs.size() == MAX_CHILDREN ) return;
175 1257477 : fake_rec * rec = NULL;
176 1324362 : do {
177 1324362 : rec = fake_rec::make_random();
178 : /* Prevent duplicate keys */
179 1324362 : } while (!txn->insert(rec));
180 :
181 1257477 : fd_funk_txn_t * txn2 = get_real_txn(txn);
182 1257477 : auto key = rec->real_id();
183 1257477 : fd_funk_rec_prepare_t prepare[1];
184 1257477 : fd_funk_rec_t * rec2 = fd_funk_rec_prepare(_real, txn2, &key, prepare, NULL);
185 1257477 : void * val = fd_funk_val_truncate(rec2, fd_funk_alloc( _real ), _wksp, 0UL, rec->size(), NULL);
186 1257477 : memcpy(val, rec->data(), rec->size());
187 1257477 : fd_funk_rec_publish( _real, prepare );
188 1257477 : assert(fd_funk_val_sz(rec2) == rec->size());
189 1257477 : }
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 2205690 : if (!i->_erased)
198 1903635 : list[listlen++] = i;
199 300000 : if (!listlen) return;
200 288489 : auto* rec = list[((uint)lrand48())%listlen];
201 :
202 288489 : fd_funk_txn_t * txn2 = get_real_txn(txn);
203 288489 : auto key = rec->real_id();
204 288489 : assert(fd_funk_rec_remove(_real, txn2, &key, NULL, 0UL) == FD_FUNK_SUCCESS);
205 :
206 288489 : rec->_erased = true;
207 288489 : rec->_data.clear();
208 288489 : }
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 3865830 : 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 210366 : void fake_cancel_family(fake_txn* txn) {
232 210366 : assert(txn->_key != ROOT_KEY);
233 358005 : while (!txn->_children.empty())
234 147639 : fake_cancel_family(txn->_children.begin()->second);
235 210366 : txn->_parent->_children.erase(txn->_key);
236 210366 : _txns.erase(txn->_key);
237 210366 : delete txn;
238 210366 : }
239 :
240 29595 : void fake_publish_to_parent(fake_txn* txn) {
241 : // Move records into parent
242 29595 : auto* parent = txn->_parent;
243 134751 : for (auto i : txn->_recs) {
244 134751 : uint p = 0;
245 4364649 : for (auto j : parent->_recs) {
246 4364649 : if( i->_key == j->_key ) {
247 85530 : delete j;
248 85530 : parent->_recs.erase(parent->_recs.begin()+p);
249 85530 : break;
250 85530 : }
251 4279119 : p++;
252 4279119 : }
253 134751 : parent->insert(i);
254 134751 : }
255 29595 : txn->_recs.clear();
256 :
257 : // Cancel siblings
258 86322 : for (;;) {
259 86322 : bool repeat = false;
260 86322 : for (auto i : parent->_children)
261 120537 : if (txn != i.second) {
262 56727 : fake_cancel_family(i.second);
263 56727 : repeat = true;
264 56727 : break;
265 56727 : }
266 86322 : if (!repeat) break;
267 86322 : }
268 29595 : assert(parent->_children.size() == 1 && parent->_children[txn->_key] == txn);
269 :
270 : // Move children up
271 29595 : parent->_children.clear();
272 44826 : for (auto i : txn->_children) {
273 44826 : auto* child = i.second;
274 44826 : child->_parent = parent;
275 44826 : parent->_children[child->_key] = child;
276 44826 : }
277 :
278 29595 : _txns.erase(txn->_key);
279 29595 : delete txn;
280 29595 : }
281 :
282 17595 : void fake_publish(fake_txn* txn) {
283 17595 : assert(txn->_key != ROOT_KEY);
284 17595 : if (txn->_parent->_key != ROOT_KEY)
285 11595 : fake_publish(txn->_parent);
286 17595 : assert(txn->_parent->_key == ROOT_KEY);
287 17595 : fake_publish_to_parent(txn);
288 17595 : }
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 233724 : if (i.second->_key != ROOT_KEY)
311 221724 : 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 1948551 : for (auto i : _txns) {
346 1948551 : assert(i.first == i.second->_key);
347 18799170 : for (auto j : i.second->_recs) {
348 18799170 : j->_touched = false;
349 18799170 : }
350 1948551 : }
351 :
352 102003 : fd_funk_all_iter_t iter[1];
353 18901173 : for( fd_funk_all_iter_new( _real, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
354 18799170 : fd_funk_rec_t const * rec = fd_funk_all_iter_ele_const( iter );
355 18799170 : auto const * xid = fd_funk_rec_xid( rec );
356 18799170 : auto i = _txns.find(xid->ul[0]);
357 18799170 : assert(i != _txns.end());
358 18799170 : auto const * key = fd_funk_rec_key( rec );
359 18799170 : auto& recs = i->second->_recs;
360 562273650 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
361 18799170 : assert(j != recs.end());
362 18799170 : auto * rec2 = *j;
363 18799170 : if (rec2->_erased) {
364 3726804 : assert(rec->flags & FD_FUNK_REC_FLAG_ERASE);
365 3726804 : assert(fd_funk_val_sz(rec) == 0);
366 15072366 : } else {
367 15072366 : assert(!(rec->flags & FD_FUNK_REC_FLAG_ERASE));
368 15072366 : assert(fd_funk_val_sz(rec) == rec2->size());
369 15072366 : assert(memcmp(fd_funk_val(rec, _wksp), rec2->data(), rec2->size()) == 0);
370 15072366 : }
371 :
372 18799170 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
373 18799170 : fd_funk_txn_t * txn = fd_funk_txn_query( xid, txn_map );
374 18799170 : fd_funk_rec_query_t query[1];
375 18799170 : auto* rec3 = fd_funk_rec_query_try_global(_real, txn, rec->pair.key, NULL, query);
376 18799170 : if( ( rec->flags & FD_FUNK_REC_FLAG_ERASE ) )
377 18799170 : assert(rec3 == NULL);
378 15072366 : else
379 18799170 : assert(rec == rec3);
380 18799170 : assert(!fd_funk_rec_query_test( query ));
381 :
382 18799170 : assert(!rec2->_touched);
383 18799170 : rec2->_touched = true;
384 18799170 : }
385 :
386 1948551 : for (auto i : _txns) {
387 18799170 : for (auto j : i.second->_recs) {
388 18799170 : assert(j->_touched || j->_erased);
389 18799170 : }
390 1948551 : }
391 :
392 1948551 : for (auto i : _txns) {
393 1948551 : auto * txn = i.second;
394 1948551 : assert(i.first == txn->_key);
395 1948551 : if (txn->_key == ROOT_KEY) {
396 102003 : assert(txn->_parent == NULL);
397 1846548 : } else {
398 1846548 : assert(txn->_parent->_children.find(txn->_key)->second == txn);
399 1846548 : }
400 1948551 : txn->_touched = false;
401 1948551 : }
402 :
403 102003 : {
404 : // Root transaction
405 102003 : auto * txn2 = _txns[ROOT_KEY];
406 102003 : assert(!txn2->_touched);
407 102003 : txn2->_touched = true;
408 :
409 102003 : auto& recs = txn2->_recs;
410 102003 : for( auto const * rec = fd_funk_txn_first_rec(_real, NULL);
411 10279047 : rec;
412 10177044 : rec = fd_funk_txn_next_rec(_real, rec) ) {
413 10177044 : auto const * key = fd_funk_rec_key( rec );
414 513436308 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
415 10177044 : assert(j != recs.end());
416 10177044 : }
417 102003 : }
418 :
419 102003 : fd_funk_txn_pool_t * txn_pool = fd_funk_txn_pool( _real );
420 :
421 102003 : fd_funk_txn_all_iter_t txn_iter[1];
422 1948551 : 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 ) ) {
423 1846548 : fd_funk_txn_t const * txn = fd_funk_txn_all_iter_ele_const( txn_iter );
424 :
425 1846548 : auto i = _txns.find(txn->xid.ul[0]);
426 1846548 : assert(i != _txns.end());
427 1846548 : auto * txn2 = i->second;
428 1846548 : assert(!txn2->_touched);
429 1846548 : txn2->_touched = true;
430 :
431 1846548 : auto * parent = fd_funk_txn_parent(txn, txn_pool);
432 1846548 : if (parent == NULL)
433 1846548 : assert(ROOT_KEY == txn2->_parent->_key);
434 1502640 : else
435 1846548 : assert(parent->xid.ul[0] == txn2->_parent->_key);
436 :
437 1846548 : auto& recs = txn2->_recs;
438 1846548 : for( auto const * rec = fd_funk_txn_first_rec(_real, txn);
439 10468674 : rec;
440 8622126 : rec = fd_funk_txn_next_rec(_real, rec) ) {
441 8622126 : auto const * key = fd_funk_rec_key( rec );
442 48837342 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
443 8622126 : assert(j != recs.end());
444 8622126 : }
445 1846548 : }
446 :
447 1948551 : for (auto i : _txns) {
448 : assert(i.second->_touched);
449 1948551 : }
450 102003 : }
451 : };
|
