Line data    Source code

       1             : extern "C" {
       2             :   #include "fd_funk.h"
       3             : }
       4             : #include <map>
       5             : #include <vector>
       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             : 
      21             :     fake_rec() = delete;
      22     3150000 :     fake_rec(ulong key) : _key(key) { }
      23             : 
      24     3150000 :     static fake_rec * make_random() {
      25     3150000 :       auto * rec = new fake_rec(((ulong)lrand48())%MAX_CHILDREN);
      26     3150000 :       auto len = ((ulong)lrand48())%8UL;
      27     3150000 :       rec->_data.resize(len);
      28    14163387 :       for (ulong i = 0; i < len; ++i)
      29    11013387 :         rec->_data[i] = lrand48();
      30     3150000 :       return rec;
      31     3150000 :     }
      32             : 
      33     3871584 :     fd_funk_rec_key_t real_id() const {
      34     3871584 :       fd_funk_rec_key_t i;
      35     3871584 :       memset(&i, 0, sizeof(i));
      36     3871584 :       i.ul[0] = _key;
      37     3871584 :       return i;
      38     3871584 :     }
      39             : 
      40    83717706 :     ulong size() const {
      41    83717706 :       return _data.size()*sizeof(long);
      42    83717706 :     }
      43             : 
      44    39746673 :     const uchar* data() const {
      45    39746673 :       return (const uchar*)_data.data();
      46    39746673 :     }
      47             : };
      48             : 
      49             : struct fake_txn {
      50             :     ulong _key;
      51             :     std::map<ulong,fake_rec*> _recs;
      52             :     std::map<ulong,fake_txn*> _children;
      53             :     fake_txn * _parent = NULL;
      54             :     bool _touched = false;
      55             : 
      56      600003 :     fake_txn(ulong key) : _key(key) { }
      57      600003 :     ~fake_txn() {
      58      600003 :       for (auto i : _recs)
      59     2798130 :         delete i.second;
      60      600003 :     }
      61             : 
      62     5058495 :     fd_funk_txn_xid_t real_id() const {
      63     5058495 :       fd_funk_txn_xid_t i;
      64     5058495 :       memset(&i, 0, sizeof(i));
      65     5058495 :       i.ul[0] = _key;
      66     5058495 :       return i;
      67     5058495 :     }
      68             : 
      69     3471003 :     void insert(fake_rec* rec) {
      70     3471003 :       auto i = _recs.find(rec->_key);
      71     3471003 :       if (i != _recs.end())
      72      351870 :         delete i->second;
      73     3471003 :       _recs[rec->_key] = rec;
      74     3471003 :     }
      75             : };
      76             : 
      77             : struct fake_funk {
      78             :     fd_wksp_t * _wksp;
      79             :     fd_funk_t * _real;
      80             :     std::map<ulong,fake_txn*> _txns;
      81             :     ulong _lastxid = 0;
      82             : #ifdef TEST_FUNK_FILE
      83             :     fd_funk_close_file_args_t close_args;
      84             : #endif
      85             : 
      86           6 :     fake_funk(int * argc, char *** argv) {
      87           6 :       fd_boot( argc, argv );
      88           6 :       ulong txn_max = 128;
      89           6 :       ulong rec_max = 1<<16;
      90             : 
      91             : #ifdef TEST_FUNK_FILE
      92           3 :       _real = fd_funk_open_file( "funk_test_file", 1, 1234U, txn_max, rec_max, FD_SHMEM_GIGANTIC_PAGE_SZ, FD_FUNK_OVERWRITE, &close_args );
      93             :       _wksp = fd_funk_wksp( _real );
      94             : 
      95             : #else
      96             :       ulong  numa_idx = fd_shmem_numa_idx( 0 );
      97           3 :       _wksp = fd_wksp_new_anonymous( FD_SHMEM_GIGANTIC_PAGE_SZ, 1U, fd_shmem_cpu_idx( numa_idx ), "wksp", 0UL );
      98           3 :       void * mem = fd_wksp_alloc_laddr( _wksp, fd_funk_align(), fd_funk_footprint(), FD_FUNK_MAGIC );
      99             :       _real = fd_funk_join( fd_funk_new( mem, 1, 1234U, txn_max, rec_max ) );
     100             : #endif
     101             : 
     102           6 :       _txns[ROOT_KEY] = new fake_txn(ROOT_KEY);
     103           6 :     }
     104           3 :     ~fake_funk() {
     105           3 :       for (auto i : _txns)
     106          18 :         delete i.second;
     107             : #ifdef TEST_FUNK_FILE
     108             :       fd_funk_close_file( &close_args );
     109             :       unlink( "funk_test_file" );
     110             : #endif
     111           3 :     }
     112             : 
     113             : #ifdef TEST_FUNK_FILE
     114           0 :     void reopen_file() {
     115           0 :       fd_funk_close_file( &close_args );
     116           0 :       _real = fd_funk_open_file( "funk_test_file", 1, 0, 0, 0, 0, FD_FUNK_READ_WRITE, &close_args );
     117           0 :       _wksp = fd_funk_wksp( _real );
     118           0 :     }
     119             : #endif
     120             : 
     121     3900000 :     fake_txn * pick_unfrozen_txn() {
     122     3900000 :       fake_txn* list[MAX_TXNS];
     123     3900000 :       uint listlen = 0;
     124     3900000 :       for (auto i : _txns)
     125    84843900 :         if (i.second->_children.size() == 0)
     126    42647100 :           list[listlen++] = i.second;
     127     3900000 :       return list[((uint)lrand48())%listlen];
     128     3900000 :     }
     129             : 
     130     4531584 :     fd_funk_txn_t * get_real_txn(fake_txn * txn) {
     131     4531584 :       if (txn->_key == ROOT_KEY)
     132       73089 :         return NULL;
     133     4458495 :       fd_funk_txn_t * txn_map = fd_funk_txn_map( _real, _wksp );
     134     4458495 :       auto xid = txn->real_id();
     135     4458495 :       return fd_funk_txn_query(&xid, txn_map);
     136     4531584 :     }
     137             : 
     138     3150000 :     void random_insert() {
     139     3150000 :       fake_txn * txn = pick_unfrozen_txn();
     140     3150000 :       fake_rec * rec = fake_rec::make_random();
     141     3150000 :       txn->insert(rec);
     142             : 
     143     3150000 :       fd_funk_start_write(_real);
     144     3150000 :       fd_funk_txn_t * txn2 = get_real_txn(txn);
     145     3150000 :       auto key = rec->real_id();
     146     3150000 :       fd_funk_rec_t * rec2 = fd_funk_rec_write_prepare(_real, txn2, &key, rec->size(), 1, NULL, NULL);
     147     3150000 :       if (fd_funk_val_sz(rec2) > rec->size())
     148     1074360 :         rec2 = fd_funk_val_truncate(rec2, rec->size(), fd_funk_alloc(_real, _wksp), _wksp, NULL);
     149     3150000 :       memcpy(fd_funk_val(rec2, _wksp), rec->data(), rec->size());
     150     3150000 :       fd_funk_end_write(_real);
     151     3150000 :     }
     152             : 
     153      750000 :     void random_remove() {
     154      750000 :       fake_txn * txn = pick_unfrozen_txn();
     155      750000 :       auto& recs = txn->_recs;
     156      750000 :       fake_rec* list[MAX_CHILDREN];
     157      750000 :       uint listlen = 0;
     158      750000 :       for (auto i : recs)
     159     5275071 :         if (!i.second->_erased)
     160     4536663 :           list[listlen++] = i.second;
     161      750000 :       if (!listlen) return;
     162      721584 :       auto* rec = list[((uint)lrand48())%listlen];
     163             : 
     164      721584 :       fd_funk_start_write(_real);
     165      721584 :       fd_funk_txn_t * txn2 = get_real_txn(txn);
     166      721584 :       auto key = rec->real_id();
     167      721584 :       auto* rec2 = fd_funk_rec_query(_real, txn2, &key);
     168      721584 :       assert(rec2 != NULL);
     169           0 :       assert(fd_funk_rec_remove(_real, (fd_funk_rec_t *)rec2, 0UL) == FD_FUNK_SUCCESS);
     170             : 
     171           0 :       rec->_erased = true;
     172      721584 :       rec->_data.clear();
     173      721584 :       fd_funk_end_write(_real);
     174      721584 :     }
     175             : 
     176           0 :     void random_repart() {
     177           0 :       fake_txn * txn = pick_unfrozen_txn();
     178           0 :       auto& recs = txn->_recs;
     179           0 :       fake_rec* list[MAX_CHILDREN];
     180           0 :       uint listlen = 0;
     181           0 :       for (auto i : recs)
     182           0 :         if (!i.second->_erased)
     183           0 :           list[listlen++] = i.second;
     184           0 :       if (!listlen) return;
     185           0 :       auto* rec = list[((uint)lrand48())%listlen];
     186           0 : 
     187           0 :       fd_funk_start_write(_real);
     188           0 :       fd_funk_txn_t * txn2 = get_real_txn(txn);
     189           0 :       auto key = rec->real_id();
     190           0 :       auto* rec2 = fd_funk_rec_query(_real, txn2, &key);
     191           0 :       assert(rec2 != NULL);
     192           0 :       fd_funk_end_write(_real);
     193           0 :     }
     194             : 
     195      600000 :     void random_new_txn() {
     196      600000 :       if (_txns.size() == MAX_TXNS)
     197           0 :         return;
     198             : 
     199      600000 :       fd_funk_start_write(_real);
     200      600000 :       fake_txn* list[MAX_TXNS];
     201      600000 :       uint listlen = 0;
     202      600000 :       for (auto i : _txns)
     203     9638400 :         list[listlen++] = i.second;
     204      600000 :       auto * parent = list[((uint)lrand48())%listlen];
     205             : 
     206      600000 :       ulong key = ++_lastxid;
     207      600000 :       auto * txn = _txns[key] = new fake_txn(key);
     208             : 
     209      600000 :       txn->_parent = parent;
     210      600000 :       parent->_children[key] = txn;
     211             : 
     212      600000 :       fd_funk_txn_t * parent2 = get_real_txn(parent);
     213      600000 :       auto xid = txn->real_id();
     214      600000 :       assert(fd_funk_txn_prepare(_real, parent2, &xid, 1) != NULL);
     215           0 :       fd_funk_end_write(_real);
     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 :       fd_funk_start_write(_real);
     223      525633 :       txn->_parent->_children.erase(txn->_key);
     224      525633 :       _txns.erase(txn->_key);
     225      525633 :       delete txn;
     226      525633 :       fd_funk_end_write(_real);
     227      525633 :     }
     228             : 
     229       74352 :     void fake_publish_to_parent(fake_txn* txn) {
     230       74352 :       fd_funk_start_write(_real);
     231             :       // Move records into parent
     232       74352 :       auto* parent = txn->_parent;
     233       74352 :       for (auto i : txn->_recs)
     234      321003 :         parent->insert(i.second);
     235       74352 :       txn->_recs.clear();
     236             : 
     237             :       // Cancel siblings
     238      215628 :       for (;;) {
     239      215628 :         bool repeat = false;
     240      215628 :         for (auto i : parent->_children)
     241      300912 :           if (txn != i.second) {
     242      141276 :             fd_funk_end_write(_real);
     243      141276 :             fake_cancel_family(i.second);
     244      141276 :             fd_funk_start_write(_real);
     245      141276 :             repeat = true;
     246      141276 :             break;
     247      141276 :           }
     248      215628 :         if (!repeat) break;
     249      215628 :       }
     250       74352 :       assert(parent->_children.size() == 1 && parent->_children[txn->_key] == txn);
     251             : 
     252             :       // Move children up
     253           0 :       parent->_children.clear();
     254      113349 :       for (auto i : txn->_children) {
     255      113349 :         auto* child = i.second;
     256      113349 :         child->_parent = parent;
     257      113349 :         parent->_children[child->_key] = child;
     258      113349 :       }
     259             : 
     260       74352 :       _txns.erase(txn->_key);
     261       74352 :       delete txn;
     262       74352 :       fd_funk_end_write(_real);
     263       74352 :     }
     264             : 
     265       44352 :     void fake_publish(fake_txn* txn) {
     266       44352 :       assert(txn->_key != ROOT_KEY);
     267       44352 :       if (txn->_parent->_key != ROOT_KEY)
     268       29352 :         fake_publish(txn->_parent);
     269       44352 :       assert(txn->_parent->_key == ROOT_KEY);
     270           0 :       fake_publish_to_parent(txn);
     271       44352 :     }
     272             : 
     273             :     /*
     274             :     void fake_merge(fake_txn* txn) {
     275             :       fd_funk_start_write(_real);
     276             :       for (auto i : txn->_children) {
     277             :         auto* child = i.second;
     278             :         for (auto i : child->_recs)
     279             :           txn->insert(i.second);
     280             :         child->_recs.clear();
     281             :         _txns.erase(child->_key);
     282             :         delete child;
     283             :       }
     284             :       txn->_children.clear();
     285             :       fd_funk_end_write(_real);
     286             :     }
     287             :     */
     288             : 
     289       15000 :     void random_publish() {
     290       15000 :       fd_funk_start_write(_real);
     291       15000 :       fake_txn* list[MAX_TXNS];
     292       15000 :       uint listlen = 0;
     293       15000 :       for (auto i : _txns)
     294      435675 :         if (i.second->_key != ROOT_KEY)
     295      420675 :           list[listlen++] = i.second;
     296       15000 :       if (!listlen) return;
     297       15000 :       auto * txn = list[((uint)lrand48())%listlen];
     298             : 
     299       15000 :       fd_funk_txn_t * txn2 = get_real_txn(txn);
     300       15000 :       assert(fd_funk_txn_publish(_real, txn2, 1) > 0);
     301           0 :       fd_funk_end_write(_real);
     302             : 
     303             :       // Simulate publication
     304       15000 :       fake_publish(txn);
     305       15000 :     }
     306             : 
     307       30000 :     void random_publish_into_parent() {
     308       30000 :       fd_funk_start_write(_real);
     309       30000 :       fake_txn* list[MAX_TXNS];
     310       30000 :       uint listlen = 0;
     311       30000 :       for (auto i : _txns)
     312      582405 :         if (i.second->_key != ROOT_KEY)
     313      552405 :           list[listlen++] = i.second;
     314       30000 :       if (!listlen) {
     315           0 :         fd_funk_end_write(_real);
     316           0 :         return;
     317           0 :       }
     318       30000 :       auto * txn = list[((uint)lrand48())%listlen];
     319             : 
     320       30000 :       fd_funk_txn_t * txn2 = get_real_txn(txn);
     321       30000 :       assert(fd_funk_txn_publish_into_parent(_real, txn2, 1) == FD_FUNK_SUCCESS);
     322           0 :       fd_funk_end_write(_real);
     323             : 
     324             :       // Simulate publication
     325       30000 :       fake_publish_to_parent(txn);
     326       30000 :     }
     327             : 
     328       15000 :     void random_cancel() {
     329       15000 :       fd_funk_start_write(_real);
     330       15000 :       fake_txn* list[MAX_TXNS];
     331       15000 :       uint listlen = 0;
     332       15000 :       for (auto i : _txns)
     333      275760 :         if (i.second->_key != ROOT_KEY)
     334      260760 :           list[listlen++] = i.second;
     335       15000 :       if (!listlen) return;
     336       15000 :       auto * txn = list[((uint)lrand48())%listlen];
     337             : 
     338       15000 :       fd_funk_txn_t * txn2 = get_real_txn(txn);
     339       15000 :       assert(fd_funk_txn_cancel(_real, txn2, 1) > 0);
     340           0 :       fd_funk_end_write(_real);
     341             : 
     342             :       // Simulate cancel
     343       15000 :       fake_cancel_family(txn);
     344       15000 :     }
     345             : 
     346             : /*
     347             :     void random_merge() {
     348             :       fd_funk_start_write(_real);
     349             :       // Look for transactions with children but no grandchildren
     350             :       fake_txn* list[MAX_TXNS];
     351             :       uint listlen = 0;
     352             :       for (auto i : _txns) {
     353             :         auto* txn = i.second;
     354             :         if (txn->_children.empty()) continue;
     355             :         for (auto j : txn->_children)
     356             :           if (!j.second->_children.empty())
     357             :             goto no_good;
     358             :         list[listlen++] = i.second;
     359             :         no_good: continue;
     360             :       }
     361             :       if (!listlen) {
     362             :         fd_funk_end_write(_real);
     363             :         return;
     364             :       }
     365             :       auto * txn = list[((uint)lrand48())%listlen];
     366             : 
     367             :       fd_funk_txn_t * txn2 = get_real_txn(txn);
     368             :       assert(fd_funk_txn_merge_all_children(_real, txn2, 1) == FD_FUNK_SUCCESS);
     369             :       fd_funk_end_write(_real);
     370             : 
     371             :       // Simulate merge
     372             :       fake_merge(txn);
     373             :     }
     374             : */
     375             : 
     376           0 :     void random_safe_read() {
     377           0 :       fd_funk_rec_key_t i;
     378           0 :       memset(&i, 0, sizeof(i));
     379           0 :       i.ul[0] = ((ulong)lrand48())%MAX_CHILDREN;
     380           0 :       ulong datalen;
     381           0 :       auto* data = fd_funk_rec_query_safe(_real, &i, fd_libc_alloc_virtual(), &datalen);
     382           0 :       if( data ) free(data);
     383           0 :     }
     384             : 
     385      255000 :     void verify() {
     386      255000 :       assert(fd_funk_verify(_real) == FD_FUNK_SUCCESS);
     387             : 
     388     4861050 :       for (auto i : _txns) {
     389     4861050 :         assert(i.first == i.second->_key);
     390    46014141 :         for (auto j : i.second->_recs) {
     391    46014141 :           assert(j.first == j.second->_key);
     392           0 :           j.second->_touched = false;
     393    46014141 :         }
     394     4861050 :       }
     395             : 
     396      255000 :       fd_funk_rec_t * rec_map = fd_funk_rec_map( _real, _wksp );
     397      255000 :       for( fd_funk_rec_map_iter_t iter = fd_funk_rec_map_iter_init( rec_map );
     398    46269141 :            !fd_funk_rec_map_iter_done( rec_map, iter );
     399    46014141 :            iter = fd_funk_rec_map_iter_next( rec_map, iter ) ) {
     400    46014141 :         fd_funk_rec_t * rec = fd_funk_rec_map_iter_ele( rec_map, iter );
     401    46014141 :         auto const * xid = fd_funk_rec_xid( rec );
     402    46014141 :         auto i = _txns.find(xid->ul[0]);
     403    46014141 :         assert(i != _txns.end());
     404           0 :         auto const * key = fd_funk_rec_key( rec );
     405    46014141 :         auto& recs = i->second->_recs;
     406    46014141 :         auto j = recs.find(key->ul[0]);
     407    46014141 :         assert(j != recs.end());
     408           0 :         auto * rec2 = j->second;
     409    46014141 :         if (rec2->_erased) {
     410     9417468 :           assert(rec->flags & FD_FUNK_REC_FLAG_ERASE);
     411           0 :           assert(fd_funk_val_sz(rec) == 0);
     412    36596673 :         } else {
     413    36596673 :           assert(!(rec->flags & FD_FUNK_REC_FLAG_ERASE));
     414           0 :           assert(fd_funk_val_sz(rec) == rec2->size());
     415           0 :           assert(memcmp(fd_funk_val(rec, _wksp), rec2->data(), rec2->size()) == 0);
     416    36596673 :         }
     417             : 
     418           0 :         fd_funk_txn_t * txn_map = fd_funk_txn_map( _real, fd_funk_wksp( _real ) );
     419    46014141 :         fd_funk_txn_t * txn = fd_funk_txn_query( xid, txn_map );
     420    46014141 :         auto* rec3 = fd_funk_rec_query_global(_real, txn, rec->pair.key, NULL);
     421    46014141 :         if( ( rec->flags & FD_FUNK_REC_FLAG_ERASE ) )
     422     9417468 :           assert(rec3 == NULL);
     423    36596673 :         else
     424    36596673 :           assert(rec == rec3);
     425             : 
     426           0 :         assert(!rec2->_touched);
     427           0 :         rec2->_touched = true;
     428    46014141 :       }
     429             : 
     430     4861050 :       for (auto i : _txns) {
     431    46014141 :         for (auto j : i.second->_recs) {
     432    46014141 :           assert(j.second->_touched || j.second->_erased);
     433    46014141 :         }
     434     4861050 :       }
     435             : 
     436     4861050 :       for (auto i : _txns) {
     437     4861050 :         auto * txn = i.second;
     438     4861050 :         assert(i.first == txn->_key);
     439     4861050 :         if (txn->_key == ROOT_KEY) {
     440      255000 :           assert(txn->_parent == NULL);
     441     4606050 :         } else {
     442     4606050 :           assert(txn->_parent->_children.find(txn->_key)->second == txn);
     443     4606050 :         }
     444           0 :         txn->_touched = false;
     445     4861050 :       }
     446             : 
     447      255000 :       {
     448             :         // Root transaction
     449      255000 :         auto * txn2 = _txns[ROOT_KEY];
     450      255000 :         assert(!txn2->_touched);
     451           0 :         txn2->_touched = true;
     452             : 
     453      255000 :         auto& recs = txn2->_recs;
     454      255000 :         for( auto const * rec = fd_funk_txn_first_rec(_real, NULL);
     455    25730895 :              rec;
     456    25475895 :              rec = fd_funk_txn_next_rec(_real, rec) ) {
     457    25475895 :           auto const * key = fd_funk_rec_key( rec );
     458    25475895 :           auto j = recs.find(key->ul[0]);
     459    25475895 :           assert(j != recs.end());
     460    25475895 :         }
     461      255000 :       }
     462             : 
     463           0 :       fd_funk_txn_t * txn_map = fd_funk_txn_map( _real, _wksp );
     464      255000 :       for( fd_funk_txn_map_iter_t iter = fd_funk_txn_map_iter_init( txn_map );
     465     4861050 :            !fd_funk_txn_map_iter_done( txn_map, iter );
     466     4606050 :            iter = fd_funk_txn_map_iter_next( txn_map, iter ) ) {
     467     4606050 :         fd_funk_txn_t * txn = fd_funk_txn_map_iter_ele( txn_map, iter );
     468     4606050 :         auto i = _txns.find(txn->xid.ul[0]);
     469     4606050 :         assert(i != _txns.end());
     470           0 :         auto * txn2 = i->second;
     471     4606050 :         assert(!txn2->_touched);
     472           0 :         txn2->_touched = true;
     473             : 
     474     4606050 :         auto * parent = fd_funk_txn_parent(txn, txn_map);
     475     4606050 :         if (parent == NULL)
     476      860562 :           assert(ROOT_KEY == txn2->_parent->_key);
     477     3745488 :         else
     478     3745488 :           assert(parent->xid.ul[0] == txn2->_parent->_key);
     479             : 
     480           0 :         auto& recs = txn2->_recs;
     481     4606050 :         for( auto const * rec = fd_funk_txn_first_rec(_real, txn);
     482    25144296 :              rec;
     483    20538246 :              rec = fd_funk_txn_next_rec(_real, rec) ) {
     484    20538246 :           auto const * key = fd_funk_rec_key( rec );
     485    20538246 :           auto j = recs.find(key->ul[0]);
     486    20538246 :           assert(j != recs.end());
     487    20538246 :         }
     488     4606050 :       }
     489             : 
     490     4861050 :       for (auto i : _txns) {
     491     4861050 :         assert(i.second->_touched);
     492     4861050 :       }
     493      255000 :     }
     494             : };