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