pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/test/src/test_lfds700_stack_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_stack_state
  12     *ss;
  13
  14   struct test_element
  15     *te_array;
  16 };
  17
  18 struct test_element
  19 {
  20   struct lfds700_stack_element
  21     se;
  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_stack_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_misc_prng_state
  51     ps;
  52
  53   struct lfds700_stack_element
  54     *se;
  55
  56   struct lfds700_stack_state
  57     ss;
  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 stack
  82
  83            we then create one thread per CPU, where each thread
  84            pushes 100,000 elements each as quickly as possible to the stack
  85            (the threads themselves alloc these elements, to obtain NUMA closeness)
  86
  87            the data pushed is a counter and a thread ID
  88
  89            the threads exit when the stack is full
  90
  91            we then validate the stack;
  92
  93            checking that the counts increment on a per unique ID basis
  94            and that the number of elements we pop equals 100,000 per thread
  95            (since each element has an incrementing counter which is
  96             unique on a per unique ID basis, we can know we didn't lose
  97             any elements)
  98
  99            there's no CAS+GC code, as we only push
 100   */
 101
 102   internal_display_test_name( "Pushing" );
 103
 104   lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 105
 106   lfds700_misc_prng_init( &ps );
 107
 108   number_elements = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors );
 109
 110   ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors );
 111
 112   // TRD : the main stack
 113   lfds700_stack_init_valid_on_current_logical_core( &ss, NULL );
 114
 115   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 116   {
 117     (ts+loop)->ss = &ss;
 118     (ts+loop)->thread_number = loop;
 119     (ts+loop)->number_elements = number_elements;
 120   }
 121
 122   thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors );
 123
 124   util_thread_starter_new( &tts, number_logical_processors );
 125
 126   LFDS700_MISC_BARRIER_STORE;
 127
 128   lfds700_misc_force_store();
 129
 130   loop = 0;
 131   lasue = NULL;
 132
 133   while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
 134   {
 135     lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 136     util_thread_starter_start( tts, &thread_handles[loop], loop, lp, thread_pushing, ts+loop );
 137     loop++;
 138   }
 139
 140   util_thread_starter_run( tts );
 141
 142   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 143     test_pal_thread_wait( thread_handles[loop] );
 144
 145   util_thread_starter_delete( tts );
 146
 147   free( thread_handles );
 148
 149   LFDS700_MISC_BARRIER_LOAD;
 150
 151   // TRD : the stack is now fully pushed; time to verify
 152   per_thread_counters = util_malloc_wrapper( sizeof(lfds700_pal_uint_t) * number_logical_processors );
 153
 154   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 155     *(per_thread_counters+loop) = number_elements - 1;
 156
 157   vi.min_elements = vi.max_elements = number_elements * number_logical_processors;
 158
 159   lfds700_stack_query( &ss, LFDS700_STACK_QUERY_SINGLETHREADED_VALIDATE, &vi, &dvs );
 160
 161   while( dvs == LFDS700_MISC_VALIDITY_VALID and lfds700_stack_pop(&ss, &se, &ps) )
 162   {
 163     te = LFDS700_STACK_GET_VALUE_FROM_ELEMENT( *se );
 164
 165     if( first_te == NULL )
 166       first_te = te;
 167
 168     if( te->thread_number >= number_logical_processors )
 169     {
 170       dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
 171       break;
 172     }
 173
 174     if( te->datum > per_thread_counters[te->thread_number] )
 175       dvs = LFDS700_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 176
 177     if( te->datum < per_thread_counters[te->thread_number] )
 178       dvs = LFDS700_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 179
 180     if( te->datum == per_thread_counters[te->thread_number] )
 181       per_thread_counters[te->thread_number]--;
 182   }
 183
 184   // TRD : clean up
 185   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 186     util_aligned_free( (ts+loop)->te_array );
 187
 188   free( per_thread_counters );
 189
 190   free( ts );
 191
 192   lfds700_stack_cleanup( &ss, NULL );
 193
 194   // TRD : print the test result
 195   internal_display_test_result( 1, "stack", dvs );
 196
 197   return;
 198 }
 199
 200
 201
 202
 203
 204 /****************************************************************************/
 205 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_pushing( void *util_thread_starter_thread_state )
 206 {
 207   lfds700_pal_uint_t
 208     loop;
 209
 210   struct lfds700_misc_prng_state
 211     ps;
 212
 213   struct test_state
 214     *ts;
 215
 216   struct util_thread_starter_thread_state
 217     *tsts;
 218
 219   LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 220
 221   assert( util_thread_starter_thread_state != NULL );
 222
 223   tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
 224   ts = (struct test_state *) tsts->thread_user_state;
 225
 226   lfds700_misc_prng_init( &ps );
 227
 228   // TRD : alloc local 100,000 elements
 229   ts->te_array = util_aligned_malloc( sizeof(struct test_element) * ts->number_elements, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
 230
 231   for( loop = 0 ; loop < ts->number_elements ; loop++ )
 232   {
 233     (ts->te_array+loop)->thread_number = ts->thread_number;
 234     (ts->te_array+loop)->datum = loop;
 235   }
 236
 237   util_thread_starter_ready_and_wait( tsts );
 238
 239   for( loop = 0 ; loop < ts->number_elements ; loop++ )
 240   {
 241     LFDS700_STACK_SET_VALUE_IN_ELEMENT( (ts->te_array+loop)->se, ts->te_array+loop );
 242     lfds700_stack_push( ts->ss, &(ts->te_array+loop)->se, &ps );
 243   }
 244
 245   LFDS700_MISC_BARRIER_STORE;
 246
 247   lfds700_misc_force_store();
 248
 249   return( (test_pal_thread_return_t) EXIT_SUCCESS );
 250 }
 251