Line data Source code
1 : extern "C" {
2 : #include "fd_funkier.h"
3 : }
4 : #include <map>
5 : #include <vector>
6 : #include <set>
7 : #include <algorithm>
8 : #include <stdlib.h>
9 : #include <assert.h>
10 : #include <unistd.h>
11 :
12 : static const long ROOT_KEY = 0;
13 : static const ulong MAX_TXNS = 100;
14 : static const ulong MAX_CHILDREN = 100;
15 : static const uint MAX_PARTS = 8;
16 :
17 : struct fake_rec {
18 : ulong _key;
19 : std::vector<long> _data;
20 : bool _erased = false;
21 : bool _touched = false;
22 : static std::set<fake_rec*> _all;
23 :
24 : fake_rec() = delete;
25 : fake_rec(ulong key) : _key(key) {
26 : assert(_all.count(this) == 0);
27 : _all.insert(this);
28 : }
29 0 : ~fake_rec() {
30 0 : assert(_all.count(this) == 1);
31 0 : _all.erase(this);
32 0 : }
33 :
34 3150000 : static fake_rec * make_random() {
35 3150000 : auto * rec = new fake_rec(((ulong)lrand48())%MAX_CHILDREN);
36 3150000 : auto len = ((ulong)lrand48())%8UL;
37 3150000 : rec->_data.resize(len);
38 14163387 : for (ulong i = 0; i < len; ++i)
39 11013387 : rec->_data[i] = lrand48();
40 3150000 : return rec;
41 3150000 : }
42 :
43 3871584 : fd_funkier_rec_key_t real_id() const {
44 3871584 : fd_funkier_rec_key_t i;
45 3871584 : memset(&i, 0, sizeof(i));
46 3871584 : i.ul[0] = _key;
47 3871584 : return i;
48 3871584 : }
49 :
50 83717706 : ulong size() const {
51 83717706 : return _data.size()*sizeof(long);
52 83717706 : }
53 :
54 39746673 : const uchar* data() const {
55 39746673 : return (const uchar*)_data.data();
56 39746673 : }
57 : };
58 :
59 : std::set<fake_rec*> fake_rec::_all;
60 :
61 : struct fake_txn {
62 : ulong _key;
63 : std::vector<fake_rec*> _recs;
64 : std::map<ulong,fake_txn*> _children;
65 : fake_txn * _parent = NULL;
66 : bool _touched = false;
67 :
68 600003 : fake_txn(ulong key) : _key(key) { }
69 600003 : ~fake_txn() {
70 2798130 : for (auto i : _recs) {
71 2798130 : delete i;
72 2798130 : }
73 600003 : }
74 :
75 5058495 : fd_funkier_txn_xid_t real_id() const {
76 5058495 : fd_funkier_txn_xid_t i;
77 5058495 : memset(&i, 0, sizeof(i));
78 5058495 : i.ul[0] = _key;
79 5058495 : return i;
80 5058495 : }
81 :
82 : bool insert(fake_rec* rec) {
83 : for (auto i : _recs)
84 : if( i->_key == rec->_key ) {
85 : delete rec;
86 : return false; /* Error */
87 : }
88 : auto sz = _recs.size();
89 : _recs.resize(sz+1);
90 : _recs[sz] = rec;
91 : return true;
92 : }
93 : };
94 :
95 : struct fake_funk {
96 : fd_wksp_t * _wksp;
97 : fd_funkier_t * _real;
98 : std::map<ulong,fake_txn*> _txns;
99 : ulong _lastxid = 0;
100 : #ifdef TEST_FUNKIER_FILE
101 : fd_funkier_close_file_args_t close_args;
102 : #endif
103 :
104 6 : fake_funk(int * argc, char *** argv) {
105 6 : fd_boot( argc, argv );
106 6 : ulong txn_max = 128;
107 6 : ulong rec_max = 1<<16;
108 :
109 : #ifdef TEST_FUNKIER_FILE
110 3 : _real = fd_funkier_open_file( "funk_test_file", 1, 1234U, txn_max, rec_max, FD_SHMEM_GIGANTIC_PAGE_SZ, FD_FUNKIER_OVERWRITE, &close_args );
111 : _wksp = fd_funkier_wksp( _real );
112 :
113 : #else
114 : ulong numa_idx = fd_shmem_numa_idx( 0 );
115 3 : _wksp = fd_wksp_new_anonymous( FD_SHMEM_GIGANTIC_PAGE_SZ, 1U, fd_shmem_cpu_idx( numa_idx ), "wksp", 0UL );
116 3 : void * mem = fd_wksp_alloc_laddr( _wksp, fd_funkier_align(), fd_funkier_footprint( txn_max, rec_max ), FD_FUNKIER_MAGIC );
117 : _real = fd_funkier_join( fd_funkier_new( mem, 1, 1234U, txn_max, rec_max ) );
118 : #endif
119 :
120 6 : _txns[ROOT_KEY] = new fake_txn(ROOT_KEY);
121 6 : }
122 : ~fake_funk() {
123 : for (auto i : _txns)
124 : delete i.second;
125 : #ifdef TEST_FUNKIER_FILE
126 : fd_funkier_close_file( &close_args );
127 : unlink( "funk_test_file" );
128 : #endif
129 : for( auto i : fake_rec::_all )
130 : FD_LOG_NOTICE(( "leaked record 0x%lx!", (ulong)i ));
131 :
132 : }
133 :
134 : #ifdef TEST_FUNKIER_FILE
135 0 : void reopen_file() {
136 0 : fd_funkier_close_file( &close_args );
137 0 : _real = fd_funkier_open_file( "funk_test_file", 1, 0, 0, 0, 0, FD_FUNKIER_READ_WRITE, &close_args );
138 0 : _wksp = fd_funkier_wksp( _real );
139 0 : }
140 : #endif
141 :
142 3900000 : fake_txn * pick_unfrozen_txn() {
143 3900000 : fake_txn* list[MAX_TXNS];
144 3900000 : uint listlen = 0;
145 3900000 : for (auto i : _txns)
146 84843900 : if (i.second->_children.size() == 0)
147 42647100 : list[listlen++] = i.second;
148 3900000 : return list[((uint)lrand48())%listlen];
149 3900000 : }
150 :
151 4531584 : fd_funkier_txn_t * get_real_txn(fake_txn * txn) {
152 4531584 : if (txn->_key == ROOT_KEY)
153 73089 : return NULL;
154 4458495 : fd_funkier_txn_map_t txn_map = fd_funkier_txn_map( _real, _wksp );
155 4458495 : auto xid = txn->real_id();
156 4458495 : return fd_funkier_txn_query(&xid, &txn_map);
157 4531584 : }
158 :
159 : void random_insert() {
160 : fake_txn * txn = pick_unfrozen_txn();
161 : if( txn->_recs.size() == MAX_CHILDREN ) return;
162 : fake_rec * rec = NULL;
163 : do {
164 : rec = fake_rec::make_random();
165 : /* Prevent duplicate keys */
166 : } while (!txn->insert(rec));
167 :
168 : fd_funkier_txn_t * txn2 = get_real_txn(txn);
169 : auto key = rec->real_id();
170 : fd_funkier_rec_prepare_t prepare[1];
171 : fd_funkier_rec_t * rec2 = fd_funkier_rec_prepare(_real, txn2, &key, prepare, NULL);
172 : void * val = fd_funkier_val_truncate(rec2, rec->size(), fd_funkier_alloc(_real, _wksp), _wksp, NULL);
173 : memcpy(val, rec->data(), rec->size());
174 : fd_funkier_rec_publish( prepare );
175 : assert(fd_funkier_val_sz(rec2) == rec->size());
176 : }
177 :
178 : void random_remove() {
179 : fake_txn * txn = pick_unfrozen_txn();
180 : auto& recs = txn->_recs;
181 : fake_rec* list[MAX_CHILDREN];
182 : uint listlen = 0;
183 : for (auto i : recs)
184 : if (!i->_erased)
185 : list[listlen++] = i;
186 : if (!listlen) return;
187 : auto* rec = list[((uint)lrand48())%listlen];
188 :
189 : fd_funkier_txn_t * txn2 = get_real_txn(txn);
190 : auto key = rec->real_id();
191 : assert(fd_funkier_rec_remove(_real, txn2, &key, NULL, 0UL) == FD_FUNKIER_SUCCESS);
192 :
193 : rec->_erased = true;
194 : rec->_data.clear();
195 : }
196 :
197 600000 : void random_new_txn() {
198 600000 : if (_txns.size() == MAX_TXNS)
199 0 : return;
200 :
201 600000 : fake_txn* list[MAX_TXNS];
202 600000 : uint listlen = 0;
203 600000 : for (auto i : _txns)
204 9638400 : list[listlen++] = i.second;
205 600000 : auto * parent = list[((uint)lrand48())%listlen];
206 :
207 600000 : ulong key = ++_lastxid;
208 600000 : auto * txn = _txns[key] = new fake_txn(key);
209 :
210 600000 : txn->_parent = parent;
211 600000 : parent->_children[key] = txn;
212 :
213 600000 : fd_funkier_txn_t * parent2 = get_real_txn(parent);
214 600000 : auto xid = txn->real_id();
215 600000 : assert(fd_funkier_txn_prepare(_real, parent2, &xid, 1) != NULL);
216 600000 : }
217 :
218 525633 : void fake_cancel_family(fake_txn* txn) {
219 525633 : assert(txn->_key != ROOT_KEY);
220 894990 : while (!txn->_children.empty())
221 369357 : fake_cancel_family(txn->_children.begin()->second);
222 525633 : txn->_parent->_children.erase(txn->_key);
223 525633 : _txns.erase(txn->_key);
224 525633 : delete txn;
225 525633 : }
226 :
227 : void fake_publish_to_parent(fake_txn* txn) {
228 : // Move records into parent
229 : auto* parent = txn->_parent;
230 : for (auto i : txn->_recs) {
231 : uint p = 0;
232 : for (auto j : parent->_recs) {
233 : if( i->_key == j->_key ) {
234 : delete j;
235 : parent->_recs.erase(parent->_recs.begin()+p);
236 : break;
237 : }
238 : p++;
239 : }
240 : parent->insert(i);
241 : }
242 : txn->_recs.clear();
243 :
244 : // Cancel siblings
245 : for (;;) {
246 : bool repeat = false;
247 : for (auto i : parent->_children)
248 : if (txn != i.second) {
249 : fake_cancel_family(i.second);
250 : repeat = true;
251 : break;
252 : }
253 : if (!repeat) break;
254 : }
255 : assert(parent->_children.size() == 1 && parent->_children[txn->_key] == txn);
256 :
257 : // Move children up
258 : parent->_children.clear();
259 : for (auto i : txn->_children) {
260 : auto* child = i.second;
261 : child->_parent = parent;
262 : parent->_children[child->_key] = child;
263 : }
264 :
265 : _txns.erase(txn->_key);
266 : delete txn;
267 : }
268 :
269 44352 : void fake_publish(fake_txn* txn) {
270 44352 : assert(txn->_key != ROOT_KEY);
271 44352 : if (txn->_parent->_key != ROOT_KEY)
272 29352 : fake_publish(txn->_parent);
273 44352 : assert(txn->_parent->_key == ROOT_KEY);
274 0 : fake_publish_to_parent(txn);
275 44352 : }
276 :
277 0 : void random_publish() {
278 0 : fake_txn* list[MAX_TXNS];
279 0 : uint listlen = 0;
280 0 : for (auto i : _txns)
281 0 : if (i.second->_key != ROOT_KEY)
282 0 : list[listlen++] = i.second;
283 0 : if (!listlen) return;
284 0 : auto * txn = list[((uint)lrand48())%listlen];
285 0 :
286 0 : fd_funkier_txn_t * txn2 = get_real_txn(txn);
287 0 : assert(fd_funkier_txn_publish(_real, txn2, 1) > 0);
288 0 :
289 0 : // Simulate publication
290 0 : fake_publish(txn);
291 0 : }
292 :
293 30000 : void random_publish_into_parent() {
294 30000 : fake_txn* list[MAX_TXNS];
295 30000 : uint listlen = 0;
296 30000 : for (auto i : _txns)
297 582405 : if (i.second->_key != ROOT_KEY)
298 552405 : list[listlen++] = i.second;
299 30000 : if (!listlen) {
300 0 : return;
301 0 : }
302 30000 : auto * txn = list[((uint)lrand48())%listlen];
303 :
304 30000 : fd_funkier_txn_t * txn2 = get_real_txn(txn);
305 30000 : assert(fd_funkier_txn_publish_into_parent(_real, txn2, 1) == FD_FUNKIER_SUCCESS);
306 :
307 : // Simulate publication
308 0 : fake_publish_to_parent(txn);
309 30000 : }
310 :
311 0 : void random_cancel() {
312 0 : fake_txn* list[MAX_TXNS];
313 0 : uint listlen = 0;
314 0 : for (auto i : _txns)
315 0 : if (i.second->_key != ROOT_KEY)
316 0 : list[listlen++] = i.second;
317 0 : if (!listlen) return;
318 0 : auto * txn = list[((uint)lrand48())%listlen];
319 0 :
320 0 : fd_funkier_txn_t * txn2 = get_real_txn(txn);
321 0 : assert(fd_funkier_txn_cancel(_real, txn2, 1) > 0);
322 0 :
323 0 : // Simulate cancel
324 0 : fake_cancel_family(txn);
325 0 : }
326 :
327 0 : void verify() {
328 : #ifdef FD_FUNKIER_HANDHOLDING
329 : assert(fd_funkier_verify(_real) == FD_FUNKIER_SUCCESS);
330 : #endif
331 :
332 0 : for (auto i : _txns) {
333 0 : assert(i.first == i.second->_key);
334 0 : for (auto j : i.second->_recs) {
335 0 : j->_touched = false;
336 0 : }
337 0 : }
338 :
339 0 : fd_funkier_all_iter_t iter[1];
340 0 : for( fd_funkier_all_iter_new( _real, iter ); !fd_funkier_all_iter_done( iter ); fd_funkier_all_iter_next( iter ) ) {
341 0 : fd_funkier_rec_t const * rec = fd_funkier_all_iter_ele_const( iter );
342 0 : auto const * xid = fd_funkier_rec_xid( rec );
343 0 : auto i = _txns.find(xid->ul[0]);
344 0 : assert(i != _txns.end());
345 0 : auto const * key = fd_funkier_rec_key( rec );
346 0 : auto& recs = i->second->_recs;
347 0 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
348 0 : assert(j != recs.end());
349 0 : auto * rec2 = *j;
350 0 : if (rec2->_erased) {
351 0 : assert(rec->flags & FD_FUNKIER_REC_FLAG_ERASE);
352 0 : assert(fd_funkier_val_sz(rec) == 0);
353 0 : } else {
354 0 : assert(!(rec->flags & FD_FUNKIER_REC_FLAG_ERASE));
355 0 : assert(fd_funkier_val_sz(rec) == rec2->size());
356 0 : assert(memcmp(fd_funkier_val(rec, _wksp), rec2->data(), rec2->size()) == 0);
357 0 : }
358 :
359 0 : fd_funkier_txn_map_t txn_map = fd_funkier_txn_map( _real, fd_funkier_wksp( _real ) );
360 0 : fd_funkier_txn_t * txn = fd_funkier_txn_query( xid, &txn_map );
361 0 : fd_funkier_rec_query_t query[1];
362 0 : auto* rec3 = fd_funkier_rec_query_try_global(_real, txn, rec->pair.key, NULL, query);
363 0 : if( ( rec->flags & FD_FUNKIER_REC_FLAG_ERASE ) )
364 0 : assert(rec3 == NULL);
365 0 : else
366 0 : assert(rec == rec3);
367 0 : assert(!fd_funkier_rec_query_test( query ));
368 :
369 0 : assert(!rec2->_touched);
370 0 : rec2->_touched = true;
371 0 : }
372 :
373 0 : for (auto i : _txns) {
374 0 : for (auto j : i.second->_recs) {
375 0 : assert(j->_touched || j->_erased);
376 0 : }
377 0 : }
378 :
379 0 : for (auto i : _txns) {
380 0 : auto * txn = i.second;
381 0 : assert(i.first == txn->_key);
382 0 : if (txn->_key == ROOT_KEY) {
383 0 : assert(txn->_parent == NULL);
384 0 : } else {
385 0 : assert(txn->_parent->_children.find(txn->_key)->second == txn);
386 0 : }
387 0 : txn->_touched = false;
388 0 : }
389 :
390 0 : {
391 : // Root transaction
392 0 : auto * txn2 = _txns[ROOT_KEY];
393 0 : assert(!txn2->_touched);
394 0 : txn2->_touched = true;
395 :
396 0 : auto& recs = txn2->_recs;
397 0 : for( auto const * rec = fd_funkier_txn_first_rec(_real, NULL);
398 0 : rec;
399 0 : rec = fd_funkier_txn_next_rec(_real, rec) ) {
400 0 : auto const * key = fd_funkier_rec_key( rec );
401 0 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
402 0 : assert(j != recs.end());
403 0 : }
404 0 : }
405 :
406 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( _real, _wksp );
407 :
408 0 : fd_funkier_txn_all_iter_t txn_iter[1];
409 0 : for( fd_funkier_txn_all_iter_new( _real, txn_iter ); !fd_funkier_txn_all_iter_done( txn_iter ); fd_funkier_txn_all_iter_next( txn_iter ) ) {
410 0 : fd_funkier_txn_t const * txn = fd_funkier_txn_all_iter_ele_const( txn_iter );
411 :
412 0 : auto i = _txns.find(txn->xid.ul[0]);
413 0 : assert(i != _txns.end());
414 0 : auto * txn2 = i->second;
415 0 : assert(!txn2->_touched);
416 0 : txn2->_touched = true;
417 :
418 0 : auto * parent = fd_funkier_txn_parent(txn, &txn_pool);
419 0 : if (parent == NULL)
420 0 : assert(ROOT_KEY == txn2->_parent->_key);
421 0 : else
422 0 : assert(parent->xid.ul[0] == txn2->_parent->_key);
423 :
424 0 : auto& recs = txn2->_recs;
425 0 : for( auto const * rec = fd_funkier_txn_first_rec(_real, txn);
426 0 : rec;
427 0 : rec = fd_funkier_txn_next_rec(_real, rec) ) {
428 0 : auto const * key = fd_funkier_rec_key( rec );
429 0 : auto j = std::find_if(recs.begin(), recs.end(), [key](auto * rec2) {return rec2->_key == key->ul[0];});
430 0 : assert(j != recs.end());
431 0 : }
432 0 : }
433 :
434 0 : for (auto i : _txns) {
435 0 : assert(i.second->_touched);
436 0 : }
437 0 : }
438 : };
|
