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

   1 /***** includes *****/
   2 #include "libtest_tests_internal.h"
   3
   4 /***** structs *****/
   5 struct test_per_thread_state
   6 {
   7   struct lfds710_freelist_state
   8     *fs;
   9
  10   struct lfds710_prng_st_state
  11     psts;
  12 };
  13
  14 struct test_element
  15 {
  16   struct lfds710_freelist_element
  17     fe;
  18
  19   lfds710_pal_uint_t
  20     datum;
  21 };
  22
  23 /***** private prototypes *****/
  24 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_rapid_popping_and_pushing( void *libshared_threads_thread_state );
  25
  26
  27
  28
  29
  30 /****************************************************************************/
  31 void libtest_tests_freelist_ea_rapid_popping_and_pushing( struct lfds710_list_asu_state *list_of_logical_processors, struct libshared_memory_state *ms, enum lfds710_misc_validity *dvs )
  32 {
  33   lfds710_pal_uint_t
  34     count,
  35     ea_size_in_freelist_elements,
  36     index = 0,
  37     loop,
  38     number_logical_processors,
  39     random_value,
  40     smallest_power_of_two_larger_than_or_equal_to_number_logical_processors = 2,
  41     temp_number_logical_processors;
  42
  43   struct lfds710_freelist_element * volatile
  44     (*ea)[LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS];
  45
  46   struct lfds710_list_asu_element
  47     *lasue = NULL;
  48
  49   struct lfds710_misc_validation_info
  50     vi;
  51
  52   struct lfds710_prng_st_state
  53     psts;
  54
  55   struct lfds710_freelist_state
  56     fs;
  57
  58   struct libtest_logical_processor
  59     *lp;
  60
  61   struct libtest_threadset_per_thread_state
  62     *pts;
  63
  64   struct libtest_threadset_state
  65     ts;
  66
  67   struct test_element
  68     *te_array;
  69
  70   struct test_per_thread_state
  71     *tpts;
  72
  73   LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
  74   LFDS710_PAL_ASSERT( ms != NULL );
  75   LFDS710_PAL_ASSERT( dvs != NULL );
  76
  77   /* TRD : in these tests there is a fundamental antagonism between
  78            how much checking/memory clean up that we do and the
  79            likelyhood of collisions between threads in their lock-free
  80            operations
  81
  82            the lock-free operations are very quick; if we do anything
  83            much at all between operations, we greatly reduce the chance
  84            of threads colliding
  85
  86            so we have some tests which do enough checking/clean up that
  87            they can tell the freelist is valid and don't leak memory
  88            and here, this test now is one of thofe which does minimal
  89            checking - in fact, the nature of the test is that you can't
  90            do any real checking - but goes very quickly
  91
  92            what we do is create a small freelist and then run one thread
  93            per CPU, where each thread simply pushes and then immediately
  94            pops
  95
  96            the test runs for ten feconds
  97
  98            after the test is done, the only check we do is to traverfe
  99            the freelist, checking for loops and ensuring the number of
 100            elements is correct
 101   */
 102
 103   *dvs = LFDS710_MISC_VALIDITY_VALID;
 104
 105   lfds710_prng_st_init( &psts, LFDS710_PRNG_SEED );
 106
 107   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 108
 109   temp_number_logical_processors = number_logical_processors >> 2;
 110   while( temp_number_logical_processors != 0 )
 111   {
 112     temp_number_logical_processors >>= 1;
 113     smallest_power_of_two_larger_than_or_equal_to_number_logical_processors <<= 1;
 114   }
 115
 116   // TRD : allocate
 117   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 118   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 119   ea = 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 );
 120
 121   lfds710_freelist_init_valid_on_current_logical_core( &fs, ea, smallest_power_of_two_larger_than_or_equal_to_number_logical_processors, NULL );
 122   lfds710_freelist_query( &fs, LFDS710_FREELIST_QUERY_GET_ELIMINATION_ARRAY_EXTRA_ELEMENTS_IN_FREELIST_ELEMENTS, NULL, (void *) &ea_size_in_freelist_elements );
 123
 124   te_array = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_element) * (number_logical_processors + ea_size_in_freelist_elements), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 125
 126   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 127   {
 128     tpts[loop].fs = &fs;
 129     LFDS710_PRNG_ST_GENERATE( psts, random_value );
 130     LFDS710_PRNG_ST_MIXING_FUNCTION( random_value );
 131     lfds710_prng_st_init( &tpts[loop].psts, random_value );
 132   }
 133
 134   for( loop = 0 ; loop < (number_logical_processors + ea_size_in_freelist_elements) ; loop++ )
 135   {
 136     LFDS710_FREELIST_SET_VALUE_IN_ELEMENT( te_array[loop].fe, &te_array[loop] );
 137     lfds710_freelist_push( &fs, &te_array[loop].fe, &psts );
 138   }
 139
 140   lfds710_freelist_query( &fs, LFDS710_FREELIST_QUERY_SINGLETHREADED_GET_COUNT, NULL, (void *) &count );
 141
 142   // TRD : get the threads ready
 143   libtest_threadset_init( &ts, NULL );
 144
 145   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
 146   {
 147     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 148     libtest_threadset_add_thread( &ts, &pts[index], lp, thread_rapid_popping_and_pushing, &tpts[index] );
 149     index++;
 150   }
 151
 152   // TRD : run the test
 153   libtest_threadset_run( &ts );
 154
 155   libtest_threadset_cleanup( &ts );
 156
 157   // TRD : validate
 158   LFDS710_MISC_BARRIER_LOAD;
 159
 160   vi.min_elements = vi.max_elements = (number_logical_processors + ea_size_in_freelist_elements);
 161
 162   lfds710_freelist_query( &fs, LFDS710_FREELIST_QUERY_SINGLETHREADED_VALIDATE, &vi, dvs );
 163
 164   lfds710_freelist_cleanup( &fs, NULL );
 165
 166   return;
 167 }
 168
 169
 170
 171
 172
 173 /****************************************************************************/
 174 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_rapid_popping_and_pushing( void *libtest_threadset_per_thread_state )
 175 {
 176   lfds710_pal_uint_t
 177     time_loop = 0;
 178
 179   struct lfds710_freelist_element
 180     *fe;
 181
 182   struct test_per_thread_state
 183     *tpts;
 184
 185   struct libtest_threadset_per_thread_state
 186     *pts;
 187
 188   time_t
 189     current_time,
 190     start_time;
 191
 192   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 193
 194   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 195
 196   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 197
 198   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 199
 200   libtest_threadset_thread_ready_and_wait( pts );
 201
 202   current_time = start_time = time( NULL );
 203
 204   while( current_time < start_time + TEST_DURATION_IN_SECONDS )
 205   {
 206     lfds710_freelist_pop( tpts->fs, &fe, &tpts->psts );
 207     lfds710_freelist_push( tpts->fs, fe, &tpts->psts );
 208
 209     if( time_loop++ == TIME_LOOP_COUNT )
 210     {
 211       time_loop = 0;
 212       time( &current_time );
 213     }
 214   }
 215
 216   LFDS710_MISC_BARRIER_STORE;
 217
 218   lfds710_misc_force_store();
 219
 220   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 221 }
 222