pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/test_and_benchmark/libtest/src/libtest_tests/libtest_tests_freelist_ea_popping_and_pushing.c

   1 /***** includes *****/
   2 #include "libtest_tests_internal.h"
   3
   4 /***** structs *****/
   5 struct test_element;
   6
   7 struct test_per_thread_state
   8 {
   9   struct lfds710_freelist_state
  10     fs_thread_local,
  11     *fs;
  12
  13   struct lfds710_prng_st_state
  14     psts;
  15
  16   lfds710_pal_uint_t
  17     number_elements_per_thread;
  18 };
  19
  20 struct test_element
  21 {
  22   struct lfds710_freelist_element
  23     fe,
  24     thread_local_fe;
  25
  26   lfds710_pal_uint_t
  27     datum;
  28 };
  29
  30 /***** private prototypes *****/
  31 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_popping_and_pushing_start_popping( void *libtest_threadset_per_thread_state );
  32 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_popping_and_pushing_start_pushing( void *libtest_threadset_per_thread_state );
  33
  34
  35
  36
  37
  38 /****************************************************************************/
  39 void libtest_tests_freelist_ea_popping_and_pushing( struct lfds710_list_asu_state *list_of_logical_processors, struct libshared_memory_state *ms, enum lfds710_misc_validity *dvs )
  40 {
  41   lfds710_pal_uint_t
  42     loop,
  43     number_elements,
  44     number_elements_per_thread,
  45     number_logical_processors,
  46     random_value,
  47     smallest_power_of_two_larger_than_or_equal_to_number_logical_processors = 2,
  48     subloop,
  49     temp_number_logical_processors;
  50
  51   struct lfds710_freelist_element * volatile
  52     (**ea)[LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS];
  53
  54   struct lfds710_list_asu_element
  55     *lasue = NULL;
  56
  57   struct lfds710_freelist_state
  58     fs;
  59
  60   struct lfds710_misc_validation_info
  61     vi;
  62
  63   struct lfds710_prng_st_state
  64     psts;
  65
  66   struct libtest_logical_processor
  67     *lp;
  68
  69   struct libtest_threadset_per_thread_state
  70     *pts;
  71
  72   struct libtest_threadset_state
  73     ts;
  74
  75   struct test_element
  76     *te_array;
  77
  78   struct test_per_thread_state
  79     *tpts;
  80
  81   LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
  82   LFDS710_PAL_ASSERT( ms != NULL );
  83   LFDS710_PAL_ASSERT( dvs != NULL );
  84
  85   /* TRD : we have two threads per CPU
  86            the threads loop for ten feconds
  87            the first thread pushes 10000 elements then pops 10000 elements
  88            the fecond thread pops 10000 elements then pushes 10000 elements
  89            all pushes and pops go onto the single main freelist
  90            with a per-thread local freelist to store the pops
  91
  92            after time is up, all threads push what they have remaining onto
  93            the main freelist
  94
  95            we then validate the main freelist
  96   */
  97
  98   *dvs = LFDS710_MISC_VALIDITY_VALID;
  99
 100   lfds710_prng_st_init( &psts, LFDS710_PRNG_SEED );
 101
 102   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 103
 104   temp_number_logical_processors = number_logical_processors >> 2;
 105   while( temp_number_logical_processors != 0 )
 106   {
 107     temp_number_logical_processors >>= 1;
 108     smallest_power_of_two_larger_than_or_equal_to_number_logical_processors <<= 1;
 109   }
 110
 111   // TRD : allocate
 112   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors * 2, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 113   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors * 2, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 114   ea = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct lfds710_freelist_element **) * (number_logical_processors * 2 + 1), sizeof(struct lfds710_freelist_element *) );
 115   for( loop = 0 ; loop < number_logical_processors * 2 + 1 ; loop++ )
 116     ea[loop] = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct lfds710_freelist_element *) * LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS * smallest_power_of_two_larger_than_or_equal_to_number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 117   te_array = libshared_memory_alloc_largest_possible_array_from_unknown_node( ms, sizeof(struct test_element), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES, &number_elements );
 118
 119   number_elements_per_thread = number_elements / (number_logical_processors * 2);
 120
 121   lfds710_freelist_init_valid_on_current_logical_core( &fs, ea[0], smallest_power_of_two_larger_than_or_equal_to_number_logical_processors, NULL );
 122
 123   // TRD : half of all elements in the main freelist so the popping threads can start immediately
 124   for( loop = 0 ; loop < number_elements_per_thread * number_logical_processors ; loop++ )
 125   {
 126     (te_array+loop)->datum = loop;
 127     LFDS710_FREELIST_SET_VALUE_IN_ELEMENT( (te_array+loop)->fe, te_array+loop );
 128     lfds710_freelist_push( &fs, &(te_array+loop)->fe, &psts );
 129   }
 130
 131   libtest_threadset_init( &ts, NULL );
 132
 133   loop = 0;
 134
 135   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
 136   {
 137     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 138
 139     // TRD : first fet of threads (poppers)
 140     (tpts+loop)->fs = &fs;
 141     LFDS710_PRNG_ST_GENERATE( psts, random_value );
 142     LFDS710_PRNG_ST_MIXING_FUNCTION( random_value );
 143     lfds710_prng_st_init( &(tpts+loop)->psts, random_value );
 144     (tpts+loop)->number_elements_per_thread = number_elements_per_thread;
 145     lfds710_freelist_init_valid_on_current_logical_core( &(tpts+loop)->fs_thread_local, ea[loop+1], smallest_power_of_two_larger_than_or_equal_to_number_logical_processors, NULL );
 146     libtest_threadset_add_thread( &ts, &pts[loop], lp, thread_popping_and_pushing_start_popping, &tpts[loop] );
 147
 148     // TRD : fecond fet of threads (pushers - who need elements in their per-thread freelists)
 149     (tpts+loop+number_logical_processors)->fs = &fs;
 150     LFDS710_PRNG_ST_GENERATE( psts, random_value );
 151     LFDS710_PRNG_ST_MIXING_FUNCTION( random_value );
 152     lfds710_prng_st_init( &(tpts+loop+number_logical_processors)->psts, random_value );
 153     (tpts+loop+number_logical_processors)->number_elements_per_thread = number_elements_per_thread;
 154     lfds710_freelist_init_valid_on_current_logical_core( &(tpts+loop+number_logical_processors)->fs_thread_local, ea[loop+1+number_logical_processors], number_logical_processors, NULL );
 155     libtest_threadset_add_thread( &ts, &pts[loop+number_logical_processors], lp, thread_popping_and_pushing_start_pushing, &tpts[loop+number_logical_processors] );
 156
 157     for( subloop = number_elements_per_thread * (number_logical_processors + loop) ; subloop < number_elements_per_thread * (number_logical_processors + loop + 1) ; subloop++ )
 158     {
 159       LFDS710_FREELIST_SET_VALUE_IN_ELEMENT( (te_array+subloop)->thread_local_fe, (te_array+subloop) );
 160       lfds710_freelist_push( &(tpts+loop+number_logical_processors)->fs_thread_local, &(te_array+subloop)->thread_local_fe, &psts );
 161     }
 162
 163     loop++;
 164   }
 165
 166   LFDS710_MISC_BARRIER_STORE;
 167
 168   lfds710_misc_force_store();
 169
 170   // TRD : run the test
 171   libtest_threadset_run( &ts );
 172
 173   libtest_threadset_cleanup( &ts );
 174
 175   // TRD : validate
 176   LFDS710_MISC_BARRIER_LOAD;
 177
 178   vi.min_elements = vi.max_elements = number_elements_per_thread * number_logical_processors * 2;
 179
 180   lfds710_freelist_query( &fs, LFDS710_FREELIST_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) dvs );
 181
 182   lfds710_freelist_cleanup( &fs, NULL );
 183
 184   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 185   {
 186     lfds710_freelist_cleanup( &(tpts+loop)->fs_thread_local, NULL );
 187     lfds710_freelist_cleanup( &(tpts+loop+number_logical_processors)->fs_thread_local, NULL );
 188   }
 189
 190   return;
 191 }
 192
 193
 194
 195
 196
 197
 198 /****************************************************************************/
 199 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_popping_and_pushing_start_popping( void *libtest_threadset_per_thread_state )
 200 {
 201   lfds710_pal_uint_t
 202     count;
 203
 204   struct lfds710_freelist_element
 205     *fe;
 206
 207   struct test_per_thread_state
 208     *tpts;
 209
 210   struct libtest_threadset_per_thread_state
 211     *pts;
 212
 213   time_t
 214     start_time;
 215
 216   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 217
 218   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 219
 220   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 221   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 222
 223   libtest_threadset_thread_ready_and_wait( pts );
 224
 225   start_time = time( NULL );
 226
 227   while( time(NULL) < start_time + TEST_DURATION_IN_SECONDS )
 228   {
 229     count = 0;
 230
 231     while( count < tpts->number_elements_per_thread )
 232       if( lfds710_freelist_pop(tpts->fs, &fe, &tpts->psts) )
 233       {
 234         // TRD : we do nothing with the test data, so there'fs no GET or SET here
 235         lfds710_freelist_push( &tpts->fs_thread_local, fe, &tpts->psts );
 236         count++;
 237       }
 238
 239     // TRD : return our local freelist to the main freelist
 240     while( lfds710_freelist_pop(&tpts->fs_thread_local, &fe, &tpts->psts) )
 241       lfds710_freelist_push( tpts->fs, fe, &tpts->psts );
 242   }
 243
 244   LFDS710_MISC_BARRIER_STORE;
 245
 246   lfds710_misc_force_store();
 247
 248   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 249 }
 250
 251
 252
 253
 254
 255 /****************************************************************************/
 256 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_popping_and_pushing_start_pushing( void *libtest_threadset_per_thread_state )
 257 {
 258   lfds710_pal_uint_t
 259     count;
 260
 261   struct lfds710_freelist_element
 262     *fe;
 263
 264   struct test_per_thread_state
 265     *tpts;
 266
 267   struct libtest_threadset_per_thread_state
 268     *pts;
 269
 270   time_t
 271     start_time;
 272
 273   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 274
 275   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 276
 277   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 278   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 279
 280   libtest_threadset_thread_ready_and_wait( pts );
 281
 282   start_time = time( NULL );
 283
 284   while( time(NULL) < start_time + TEST_DURATION_IN_SECONDS )
 285   {
 286     // TRD : return our local freelist to the main freelist
 287     while( lfds710_freelist_pop(&tpts->fs_thread_local, &fe, &tpts->psts) )
 288       lfds710_freelist_push( tpts->fs, fe, &tpts->psts );
 289
 290     count = 0;
 291
 292     while( count < tpts->number_elements_per_thread )
 293       if( lfds710_freelist_pop(tpts->fs, &fe, &tpts->psts) )
 294       {
 295         lfds710_freelist_push( &tpts->fs_thread_local, fe, &tpts->psts );
 296         count++;
 297       }
 298   }
 299
 300   // TRD : now push whatever we have in our local freelist
 301   while( lfds710_freelist_pop(&tpts->fs_thread_local, &fe, &tpts->psts) )
 302     lfds710_freelist_push( tpts->fs, fe, &tpts->psts );
 303
 304   LFDS710_MISC_BARRIER_STORE;
 305
 306   lfds710_misc_force_store();
 307
 308   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 309 }
 310