pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/test/src/test_lfds700_freelist_pushing.c

   1 /***** includes *****/
   2 #include "internal.h"
   3
   4 /***** structs *****/
   5 struct test_state
   6 {
   7   lfds700_pal_uint_t
   8     number_elements,
   9     thread_number;
  10
  11   struct lfds700_freelist_state
  12     *fs;
  13
  14   struct test_element
  15     *te_array;
  16 };
  17
  18 struct test_element
  19 {
  20   struct lfds700_freelist_element
  21     fe;
  22
  23   lfds700_pal_uint_t
  24     datum,
  25     thread_number;
  26 };
  27
  28 /***** private prototypes *****/
  29 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_pushing( void *util_thread_starter_thread_state );
  30
  31
  32
  33
  34
  35 /****************************************************************************/
  36 void test_lfds700_freelist_pushing( struct lfds700_list_asu_state *list_of_logical_processors, lfds700_pal_uint_t memory_in_megabytes )
  37 {
  38   enum lfds700_misc_validity
  39     dvs = LFDS700_MISC_VALIDITY_VALID;
  40
  41   lfds700_pal_uint_t
  42     loop,
  43     number_elements,
  44     number_logical_processors,
  45     *per_thread_counters;
  46
  47   struct lfds700_list_asu_element
  48     *lasue;
  49
  50   struct lfds700_freelist_element
  51     *fe;
  52
  53   struct lfds700_freelist_state
  54     fs;
  55
  56   struct lfds700_misc_prng_state
  57     ps;
  58
  59   struct lfds700_misc_validation_info
  60     vi;
  61
  62   struct test_pal_logical_processor
  63     *lp;
  64
  65   struct util_thread_starter_state
  66     *tts;
  67
  68   struct test_element
  69     *te,
  70     *first_te = NULL;
  71
  72   struct test_state
  73     *ts;
  74
  75   test_pal_thread_state_t
  76     *thread_handles;
  77
  78   assert( list_of_logical_processors != NULL );
  79   // TRD : memory_in_megabytes can be any value in its range
  80
  81   /* TRD : we create an empty freelist
  82
  83            we then create one thread per CPU, where each thread
  84            pushes 100,000 elements each as quickly as possible to the freelist
  85
  86            the data pushed is a counter and a thread ID
  87
  88            the threads exit when the freelist is full
  89
  90            we then validate the freelist;
  91
  92            checking that the counts increment on a per unique ID basis
  93            and that the number of elements we pop equals 100,000 per thread
  94            (since each element has an incrementing counter which is
  95             unique on a per unique ID basis, we can know we didn't lose
  96             any elements)
  97   */
  98
  99   internal_display_test_name( "Pushing" );
 100
 101   lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 102
 103   lfds700_misc_prng_init( &ps );
 104
 105   number_elements = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors );
 106
 107   // TRD : the main freelist
 108   lfds700_freelist_init_valid_on_current_logical_core( &fs, NULL );
 109
 110   ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors );
 111
 112   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 113   {
 114     (ts+loop)->fs = &fs;
 115     (ts+loop)->thread_number = loop;
 116     (ts+loop)->number_elements = number_elements;
 117   }
 118
 119   thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors );
 120
 121   util_thread_starter_new( &tts, number_logical_processors );
 122
 123   LFDS700_MISC_BARRIER_STORE;
 124
 125   lfds700_misc_force_store();
 126
 127   loop = 0;
 128   lasue = NULL;
 129
 130   while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
 131   {
 132     lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 133     util_thread_starter_start( tts, &thread_handles[loop], loop, lp, thread_pushing, ts+loop );
 134     loop++;
 135   }
 136
 137   util_thread_starter_run( tts );
 138
 139   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 140     test_pal_thread_wait( thread_handles[loop] );
 141
 142   util_thread_starter_delete( tts );
 143
 144   free( thread_handles );
 145
 146   LFDS700_MISC_BARRIER_LOAD;
 147
 148   per_thread_counters = util_malloc_wrapper( sizeof(lfds700_pal_uint_t) * number_logical_processors );
 149
 150   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 151     *(per_thread_counters+loop) = number_elements - 1;
 152
 153   vi.min_elements = vi.max_elements = number_elements * number_logical_processors;
 154
 155   lfds700_freelist_query( &fs, LFDS700_STACK_QUERY_SINGLETHREADED_VALIDATE, &vi, &dvs );
 156
 157   while( dvs == LFDS700_MISC_VALIDITY_VALID and lfds700_freelist_pop(&fs, &fe, &ps) )
 158   {
 159     te = LFDS700_FREELIST_GET_VALUE_FROM_ELEMENT( *fe );
 160
 161     if( first_te == NULL )
 162       first_te = te;
 163
 164     if( te->thread_number >= number_logical_processors )
 165     {
 166       dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
 167       break;
 168     }
 169
 170     if( te->datum > per_thread_counters[te->thread_number] )
 171       dvs = LFDS700_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 172
 173     if( te->datum < per_thread_counters[te->thread_number] )
 174       dvs = LFDS700_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 175
 176     if( te->datum == per_thread_counters[te->thread_number] )
 177       per_thread_counters[te->thread_number]--;
 178   }
 179
 180   // TRD : clean up
 181   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 182     util_aligned_free( (ts+loop)->te_array );
 183
 184   free( per_thread_counters );
 185
 186   free( ts );
 187
 188   lfds700_freelist_cleanup( &fs, NULL );
 189
 190   // TRD : print the test result
 191   internal_display_test_result( 1, "freelist", dvs );
 192
 193   return;
 194 }
 195
 196
 197
 198
 199
 200 /****************************************************************************/
 201 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_pushing( void *util_thread_starter_thread_state )
 202 {
 203   lfds700_pal_uint_t
 204     loop;
 205
 206   struct lfds700_misc_prng_state
 207     ps;
 208
 209   struct test_state
 210     *ts;
 211
 212   struct util_thread_starter_thread_state
 213     *tsts;
 214
 215   LFDS700_MISC_BARRIER_LOAD;
 216
 217   assert( util_thread_starter_thread_state != NULL );
 218
 219   tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
 220   ts = (struct test_state *) tsts->thread_user_state;
 221
 222   lfds700_misc_prng_init( &ps );
 223
 224   ts->te_array = util_aligned_malloc( sizeof(struct test_element) * ts->number_elements, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
 225
 226   for( loop = 0 ; loop < ts->number_elements ; loop++ )
 227   {
 228     (ts->te_array+loop)->thread_number = ts->thread_number;
 229     (ts->te_array+loop)->datum = loop;
 230   }
 231
 232   util_thread_starter_ready_and_wait( tsts );
 233
 234   for( loop = 0 ; loop < ts->number_elements ; loop++ )
 235   {
 236     LFDS700_FREELIST_SET_VALUE_IN_ELEMENT( (ts->te_array+loop)->fe, ts->te_array+loop );
 237     lfds700_freelist_push( ts->fs, &(ts->te_array+loop)->fe, &ps );
 238   }
 239
 240   LFDS700_MISC_BARRIER_STORE;
 241
 242   lfds700_misc_force_store();
 243
 244   return( (test_pal_thread_return_t) EXIT_SUCCESS );
 245 }
 246