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 :
10 : static const long ROOT_KEY = 0;
11 : static const ulong MAX_TXNS = 100;
12 : static const ulong MAX_CHILDREN = 100;
13 : static const uint MAX_PARTS = 8;
14 :
15 : struct fake_rec {
16 : ulong _key;
17 : std::vector<long> _data;
18 : bool _erased = false;
19 : bool _touched = false;
20 : static std::set<fake_rec*> _all;
21 :
22 : fake_rec() = delete;
23 1324362 : fake_rec(ulong key) : _key(key) {
24 1324362 : assert(_all.count(this) == 0);
25 0 : _all.insert(this);
26 1324362 : }
27 1324362 : ~fake_rec() {
28 1324362 : assert(_all.count(this) == 1);
29 0 : _all.erase(this);
30 1324362 : }
31 :
32 1324362 : static fake_rec * make_random() {
33 1324362 : auto * rec = new fake_rec(((ulong)lrand48())%MAX_CHILDREN);
34 1324362 : auto len = ((ulong)lrand48())%8UL;
35 1324362 : rec->_data.resize(len);
36 5948328 : for (ulong i = 0; i < len; ++i)
37 4623966 : rec->_data[i] = lrand48();
38 1324362 : return rec;
39 1324362 : }
40 :
41 1545966 : fd_funk_rec_key_t real_id() const {
42 1545966 : fd_funk_rec_key_t i;
43 1545966 : memset(&i, 0, sizeof(i));
44 1545966 : i.ul[0] = _key;
45 1545966 : return i;
46 1545966 : }
47 :
48 33917163 : ulong size() const {
49 33917163 : return _data.size()*sizeof(long);
50 33917163 : }
51 :
52 16329843 : const uchar* data() const {
53 16329843 : return (const uchar*)_data.data();
54 16329843 : }
55 : };
56 :
57 : std::set<fake_rec*> fake_rec::_all;
58 :
59 : struct fake_txn {
60 : ulong _key;
61 : std::vector<fake_rec*> _recs;
62 : std::map<ulong,fake_txn*> _children;
63 : fake_txn * _parent = NULL;
64 : bool _touched = false;
65 :
66 240003 : fake_txn(ulong key) : _key(key) { }
67 240003 : ~fake_txn() {
68 1171947 : for (auto i : _recs) {
69 1171947 : delete i;
70 1171947 : }
71 240003 : }
72 :
73 2023092 : fd_funk_txn_xid_t real_id() const {
74 2023092 : fd_funk_txn_xid_t i;
75 2023092 : memset(&i, 0, sizeof(i));
76 2023092 : i.ul[0] = _key;
77 2023092 : return i;
78 2023092 : }
79 :
80 1459113 : bool insert(fake_rec* rec) {
81 1459113 : for (auto i : _recs)
82 15016125 : if( i->_key == rec->_key ) {
83 66885 : delete rec;
84 66885 : return false; /* Error */
85 66885 : }
86 1392228 : auto sz = _recs.size();
87 1392228 : _recs.resize(sz+1);
88 1392228 : _recs[sz] = rec;
89 1392228 : return true;
90 1459113 : }
91 : };
92 :
93 : struct fake_funk {
94 : fd_wksp_t * _wksp;
95 : fd_funk_t _real[1];
96 : std::map<ulong,fake_txn*> _txns;
97 : ulong _lastxid = 0;
98 :
99 3 : fake_funk(int * argc, char *** argv) {
100 3 : fd_boot( argc, argv );
101 3 : ulong txn_max = 128;
102 3 : uint rec_max = 1<<16;
103 :
104 3 : ulong numa_idx = fd_shmem_numa_idx( 0 );
105 3 : _wksp = fd_wksp_new_anonymous( FD_SHMEM_GIGANTIC_PAGE_SZ, 1U, fd_shmem_cpu_idx( numa_idx ), "wksp", 0UL );
106 3 : void * mem = fd_wksp_alloc_laddr( _wksp, fd_funk_align(), fd_funk_footprint( txn_max, rec_max ), FD_FUNK_MAGIC );
107 3 : FD_TEST( fd_funk_join( _real, fd_funk_new( mem, 1, 1234U, txn_max, rec_max ) ) );
108 :
109 3 : _txns[ROOT_KEY] = new fake_txn(ROOT_KEY);
110 3 : }
111 3 : ~fake_funk() {
112 3 : for (auto i : _txns)
113 42 : delete i.second;
114 3 : for( auto i : fake_rec::_all )
115 0 : FD_LOG_NOTICE(( "leaked record 0x%lx!", (ulong)i ));
116 :
117 3 : }
118 :
119 1560000 : fake_txn * pick_unfrozen_txn() {
120 1560000 : fake_txn* list[MAX_TXNS];
121 1560000 : uint listlen = 0;
122 1560000 : for (auto i : _txns)
123 33998520 : if (i.second->_children.size() == 0)
124 17102070 : list[listlen++] = i.second;
125 1560000 : return list[((uint)lrand48())%listlen];
126 1560000 : }
127 :
128 1809966 : fd_funk_txn_t * get_real_txn(fake_txn * txn) {
129 1809966 : if (txn->_key == ROOT_KEY)
130 26874 : return NULL;
131 1783092 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
132 1783092 : auto xid = txn->real_id();
133 1783092 : return fd_funk_txn_query(&xid, txn_map);
134 1809966 : }
135 :
136 1260000 : void random_insert() {
137 1260000 : fake_txn * txn = pick_unfrozen_txn();
138 1260000 : if( txn->_recs.size() == MAX_CHILDREN ) return;
139 1257477 : fake_rec * rec = NULL;
140 1324362 : do {
141 1324362 : rec = fake_rec::make_random();
142 : /* Prevent duplicate keys */
143 1324362 : } while (!txn->insert(rec));
144 :
145 1257477 : fd_funk_txn_t * txn2 = get_real_txn(txn);
146 1257477 : auto key = rec->real_id();
147 1257477 : fd_funk_rec_prepare_t prepare[1];
148 1257477 : fd_funk_rec_t * rec2 = fd_funk_rec_prepare(_real, txn2, &key, prepare, NULL);
149 1257477 : void * val = fd_funk_val_truncate(rec2, fd_funk_alloc( _real ), _wksp, 0UL, rec->size(), NULL);
150 1257477 : memcpy(val, rec->data(), rec->size());
151 1257477 : fd_funk_rec_publish( _real, prepare );
152 1257477 : assert(fd_funk_val_sz(rec2) == rec->size());
153 1257477 : }
154 :
155 300000 : void random_remove() {
156 300000 : fake_txn * txn = pick_unfrozen_txn();
157 300000 : auto& recs = txn->_recs;
158 300000 : fake_rec* list[MAX_CHILDREN];
159 300000 : uint listlen = 0;
160 300000 : for (auto i : recs)
161 2205690 : if (!i->_erased)
162 1903635 : list[listlen++] = i;
163 300000 : if (!listlen) return;
164 288489 : auto* rec = list[((uint)lrand48())%listlen];
165 :
166 288489 : fd_funk_txn_t * txn2 = get_real_txn(txn);
167 288489 : auto key = rec->real_id();
168 288489 : assert(fd_funk_rec_remove(_real, txn2, &key, NULL, 0UL) == FD_FUNK_SUCCESS);
169 :
170 0 : rec->_erased = true;
171 288489 : rec->_data.clear();
172 288489 : }
173 :
174 240000 : void random_new_txn() {
175 240000 : if (_txns.size() == MAX_TXNS)
176 0 : return;
177 :
178 240000 : fake_txn* list[MAX_TXNS];
179 240000 : uint listlen = 0;
180 240000 : for (auto i : _txns)
181 3865830 : list[listlen++] = i.second;
182 240000 : auto * parent = list[((uint)lrand48())%listlen];
183 :
184 240000 : ulong key = ++_lastxid;
185 240000 : auto * txn = _txns[key] = new fake_txn(key);
186 :
187 240000 : txn->_parent = parent;
188 240000 : parent->_children[key] = txn;
189 :
190 240000 : fd_funk_txn_t * parent2 = get_real_txn(parent);
191 240000 : auto xid = txn->real_id();
192 240000 : assert(fd_funk_txn_prepare(_real, parent2, &xid, 1) != NULL);
193 240000 : }
194 :
195 210366 : void fake_cancel_family(fake_txn* txn) {
196 210366 : assert(txn->_key != ROOT_KEY);
197 358005 : while (!txn->_children.empty())
198 147639 : fake_cancel_family(txn->_children.begin()->second);
199 210366 : txn->_parent->_children.erase(txn->_key);
200 210366 : _txns.erase(txn->_key);
201 210366 : delete txn;
202 210366 : }
203 :
204 29595 : void fake_publish_to_parent(fake_txn* txn) {
205 : // Move records into parent
206 29595 : auto* parent = txn->_parent;
207 134751 : for (auto i : txn->_recs) {
208 134751 : uint p = 0;
209 4364649 : for (auto j : parent->_recs) {
210 4364649 : if( i->_key == j->_key ) {
211 85530 : delete j;
212 85530 : parent->_recs.erase(parent->_recs.begin()+p);
213 85530 : break;
214 85530 : }
215 4279119 : p++;
216 4279119 : }
217 134751 : parent->insert(i);
218 134751 : }
219 29595 : txn->_recs.clear();
220 :
221 : // Cancel siblings
222 86322 : for (;;) {
223 86322 : bool repeat = false;
224 86322 : for (auto i : parent->_children)
225 120537 : if (txn != i.second) {
226 56727 : fake_cancel_family(i.second);
227 56727 : repeat = true;
228 56727 : break;
229 56727 : }
230 86322 : if (!repeat) break;
231 86322 : }
232 29595 : assert(parent->_children.size() == 1 && parent->_children[txn->_key] == txn);
233 :
234 : // Move children up
235 0 : parent->_children.clear();
236 44826 : for (auto i : txn->_children) {
237 44826 : auto* child = i.second;
238 44826 : child->_parent = parent;
239 44826 : parent->_children[child->_key] = child;
240 44826 : }
241 :
242 29595 : _txns.erase(txn->_key);
243 29595 : delete txn;
244 29595 : }
245 :
246 17595 : void fake_publish(fake_txn* txn) {
247 17595 : assert(txn->_key != ROOT_KEY);
248 17595 : if (txn->_parent->_key != ROOT_KEY)
249 11595 : fake_publish(txn->_parent);
250 17595 : assert(txn->_parent->_key == ROOT_KEY);
251 0 : fake_publish_to_parent(txn);
252 17595 : }
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 : fd_funk_txn_t * txn2 = get_real_txn(txn);
264 0 : assert(fd_funk_txn_publish(_real, txn2, 1) > 0);
265 0 :
266 0 : // Simulate publication
267 0 : fake_publish(txn);
268 0 : }
269 :
270 12000 : void random_publish_into_parent() {
271 12000 : fake_txn* list[MAX_TXNS];
272 12000 : uint listlen = 0;
273 12000 : for (auto i : _txns)
274 233724 : if (i.second->_key != ROOT_KEY)
275 221724 : list[listlen++] = i.second;
276 12000 : if (!listlen) {
277 0 : return;
278 0 : }
279 12000 : auto * txn = list[((uint)lrand48())%listlen];
280 :
281 12000 : fd_funk_txn_t * txn2 = get_real_txn(txn);
282 12000 : assert(fd_funk_txn_publish_into_parent(_real, txn2, 1) == FD_FUNK_SUCCESS);
283 :
284 : // Simulate publication
285 0 : fake_publish_to_parent(txn);
286 12000 : }
287 :
288 0 : void random_cancel() {
289 0 : fake_txn* list[MAX_TXNS];
290 0 : uint listlen = 0;
291 0 : for (auto i : _txns)
292 0 : if (i.second->_key != ROOT_KEY)
293 0 : list[listlen++] = i.second;
294 0 : if (!listlen) return;
295 0 : auto * txn = list[((uint)lrand48())%listlen];
296 0 :
297 0 : fd_funk_txn_t * txn2 = get_real_txn(txn);
298 0 : assert(fd_funk_txn_cancel(_real, txn2, 1) > 0);
299 0 :
300 0 : // Simulate cancel
301 0 : fake_cancel_family(txn);
302 0 : }
303 :
304 102003 : void verify() {
305 : #ifdef FD_FUNK_HANDHOLDING
306 : assert(fd_funk_verify(_real) == FD_FUNK_SUCCESS);
307 : #endif
308 :
309 1948551 : for (auto i : _txns) {
310 1948551 : assert(i.first == i.second->_key);
311 18799170 : for (auto j : i.second->_recs) {
312 18799170 : j->_touched = false;
313 18799170 : }
314 1948551 : }
315 :
316 102003 : fd_funk_all_iter_t iter[1];
317 18901173 : for( fd_funk_all_iter_new( _real, iter ); !fd_funk_all_iter_done( iter ); fd_funk_all_iter_next( iter ) ) {
318 18799170 : fd_funk_rec_t const * rec = fd_funk_all_iter_ele_const( iter );
319 18799170 : auto const * xid = fd_funk_rec_xid( rec );
320 18799170 : auto i = _txns.find(xid->ul[0]);
321 18799170 : assert(i != _txns.end());
322 0 : auto const * key = fd_funk_rec_key( rec );
323 18799170 : auto& recs = i->second->_recs;
324 562273650 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
325 18799170 : assert(j != recs.end());
326 0 : auto * rec2 = *j;
327 18799170 : if (rec2->_erased) {
328 3726804 : assert(rec->flags & FD_FUNK_REC_FLAG_ERASE);
329 0 : assert(fd_funk_val_sz(rec) == 0);
330 15072366 : } else {
331 15072366 : assert(!(rec->flags & FD_FUNK_REC_FLAG_ERASE));
332 0 : assert(fd_funk_val_sz(rec) == rec2->size());
333 0 : assert(memcmp(fd_funk_val(rec, _wksp), rec2->data(), rec2->size()) == 0);
334 15072366 : }
335 :
336 0 : fd_funk_txn_map_t * txn_map = fd_funk_txn_map( _real );
337 18799170 : fd_funk_txn_t * txn = fd_funk_txn_query( xid, txn_map );
338 18799170 : fd_funk_rec_query_t query[1];
339 18799170 : auto* rec3 = fd_funk_rec_query_try_global(_real, txn, rec->pair.key, NULL, query);
340 18799170 : if( ( rec->flags & FD_FUNK_REC_FLAG_ERASE ) )
341 3726804 : assert(rec3 == NULL);
342 15072366 : else
343 15072366 : assert(rec == rec3);
344 0 : assert(!fd_funk_rec_query_test( query ));
345 :
346 0 : assert(!rec2->_touched);
347 0 : rec2->_touched = true;
348 18799170 : }
349 :
350 1948551 : for (auto i : _txns) {
351 18799170 : for (auto j : i.second->_recs) {
352 18799170 : assert(j->_touched || j->_erased);
353 18799170 : }
354 1948551 : }
355 :
356 1948551 : for (auto i : _txns) {
357 1948551 : auto * txn = i.second;
358 1948551 : assert(i.first == txn->_key);
359 1948551 : if (txn->_key == ROOT_KEY) {
360 102003 : assert(txn->_parent == NULL);
361 1846548 : } else {
362 1846548 : assert(txn->_parent->_children.find(txn->_key)->second == txn);
363 1846548 : }
364 0 : txn->_touched = false;
365 1948551 : }
366 :
367 102003 : {
368 : // Root transaction
369 102003 : auto * txn2 = _txns[ROOT_KEY];
370 102003 : assert(!txn2->_touched);
371 0 : txn2->_touched = true;
372 :
373 102003 : auto& recs = txn2->_recs;
374 102003 : for( auto const * rec = fd_funk_txn_first_rec(_real, NULL);
375 10279047 : rec;
376 10177044 : rec = fd_funk_txn_next_rec(_real, rec) ) {
377 10177044 : auto const * key = fd_funk_rec_key( rec );
378 513436308 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
379 10177044 : assert(j != recs.end());
380 10177044 : }
381 102003 : }
382 :
383 0 : fd_funk_txn_pool_t * txn_pool = fd_funk_txn_pool( _real );
384 :
385 102003 : fd_funk_txn_all_iter_t txn_iter[1];
386 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 ) ) {
387 1846548 : fd_funk_txn_t const * txn = fd_funk_txn_all_iter_ele_const( txn_iter );
388 :
389 1846548 : auto i = _txns.find(txn->xid.ul[0]);
390 1846548 : assert(i != _txns.end());
391 0 : auto * txn2 = i->second;
392 1846548 : assert(!txn2->_touched);
393 0 : txn2->_touched = true;
394 :
395 1846548 : auto * parent = fd_funk_txn_parent(txn, txn_pool);
396 1846548 : if (parent == NULL)
397 343908 : assert(ROOT_KEY == txn2->_parent->_key);
398 1502640 : else
399 1502640 : assert(parent->xid.ul[0] == txn2->_parent->_key);
400 :
401 0 : auto& recs = txn2->_recs;
402 1846548 : for( auto const * rec = fd_funk_txn_first_rec(_real, txn);
403 10468674 : rec;
404 8622126 : rec = fd_funk_txn_next_rec(_real, rec) ) {
405 8622126 : auto const * key = fd_funk_rec_key( rec );
406 48837342 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
407 8622126 : assert(j != recs.end());
408 8622126 : }
409 1846548 : }
410 :
411 1948551 : for (auto i : _txns) {
412 1948551 : assert(i.second->_touched);
413 1948551 : }
414 102003 : }
415 : };
|
