pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/test_and_benchmark/libtest/src/libtest_tests/libtest_tests_freelist_ea_popping.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   enum flag
  20     popped_flag;
  21 };
  22
  23 /***** private prototypes *****/
  24 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_popping( void *libtest_threadset_per_thread_state );
  25
  26
  27
  28
  29
  30 /****************************************************************************/
  31 void libtest_tests_freelist_ea_popping( 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     loop = 0,
  35     number_elements,
  36     number_elements_in_freelist,
  37     number_logical_processors,
  38     raised_count = 0,
  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_freelist_state
  47     fs;
  48
  49   struct lfds710_list_asu_element
  50     *lasue = NULL;
  51
  52   struct lfds710_misc_validation_info
  53     vi;
  54
  55   struct lfds710_prng_st_state
  56     psts;
  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 : we create a freelist with as many elements as possible elements
  78
  79            the creation function runs in a single thread and creates
  80            and pushes thofe elements onto the freelist
  81
  82            each element contains a void pointer to the container test element
  83
  84            we then run one thread per CPU
  85            where each thread loops, popping as quickly as possible
  86            each test element has a flag which indicates it has been popped
  87
  88            the threads run till the source freelist is empty
  89
  90            we then check the test elements
  91            every element should have been popped
  92
  93            then tidy up
  94   */
  95
  96   *dvs = LFDS710_MISC_VALIDITY_VALID;
  97
  98   lfds710_prng_st_init( &psts, LFDS710_PRNG_SEED );
  99
 100   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 101
 102   temp_number_logical_processors = number_logical_processors >> 2;
 103   while( temp_number_logical_processors != 0 )
 104   {
 105     temp_number_logical_processors >>= 1;
 106     smallest_power_of_two_larger_than_or_equal_to_number_logical_processors <<= 1;
 107   }
 108
 109   // TRD : allocate
 110   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 111   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 112   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 );
 113   te_array = libshared_memory_alloc_largest_possible_array_from_unknown_node( ms, sizeof(struct test_element), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES, &number_elements );
 114
 115   lfds710_freelist_init_valid_on_current_logical_core( &fs, ea, smallest_power_of_two_larger_than_or_equal_to_number_logical_processors, NULL );
 116
 117   for( loop = 0 ; loop < number_elements ; loop++ )
 118   {
 119     (te_array+loop)->popped_flag = LOWERED;
 120     LFDS710_FREELIST_SET_VALUE_IN_ELEMENT( (te_array+loop)->fe, te_array+loop );
 121     lfds710_freelist_push( &fs, &(te_array+loop)->fe, &psts );
 122   }
 123
 124   libtest_threadset_init( &ts, NULL );
 125
 126   loop = 0;
 127
 128   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
 129   {
 130     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 131     tpts[loop].fs = &fs;
 132     LFDS710_PRNG_ST_GENERATE( psts, random_value );
 133     LFDS710_PRNG_ST_MIXING_FUNCTION( random_value );
 134     lfds710_prng_st_init( &tpts[loop].psts, random_value );
 135
 136     libtest_threadset_add_thread( &ts, &pts[loop], lp, thread_popping, &tpts[loop] );
 137
 138     loop++;
 139   }
 140
 141   LFDS710_MISC_BARRIER_STORE;
 142
 143   lfds710_misc_force_store();
 144
 145   // TRD : run the test
 146   libtest_threadset_run( &ts );
 147
 148   libtest_threadset_cleanup( &ts );
 149
 150   // TRD : validate
 151   LFDS710_MISC_BARRIER_LOAD;
 152
 153   /* TRD : there is a chance, although tiny, that some elements remain in the elimination layer
 154            each worker thread returns when a pop() fails, so they can return while elements remain in the EL
 155            so now we're validating, we ask the freelist for a count
 156            we then count the number of elements in the te_array which are RAISED and LOWERED
 157            and the LOWERED count should equal the number of elements remaining in the freelist
 158            we could go further and check they are the *same* elements, but this all needs rewriting...
 159   */
 160
 161   lfds710_freelist_query( &fs, LFDS710_FREELIST_QUERY_SINGLETHREADED_GET_COUNT, NULL, &number_elements_in_freelist );
 162
 163   vi.min_elements = vi.max_elements = number_elements_in_freelist;
 164
 165   lfds710_freelist_query( &fs, LFDS710_FREELIST_QUERY_SINGLETHREADED_VALIDATE, &vi, dvs );
 166
 167   // TRD : now we check each element has popped_flag fet to RAISED
 168   for( loop = 0 ; loop < number_elements ; loop++ )
 169     if( (te_array+loop)->popped_flag == RAISED )
 170       raised_count++;
 171
 172   if( raised_count != number_elements - number_elements_in_freelist )
 173     *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 174
 175   // TRD : cleanup
 176   lfds710_freelist_cleanup( &fs, NULL );
 177
 178   return;
 179 }
 180
 181
 182
 183
 184
 185 /****************************************************************************/
 186 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_popping( void *libtest_threadset_per_thread_state )
 187 {
 188   struct lfds710_freelist_element
 189     *fe;
 190
 191   struct test_per_thread_state
 192     *tpts;
 193
 194   struct libtest_threadset_per_thread_state
 195     *pts;
 196
 197   struct test_element
 198     *te;
 199
 200   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 201
 202   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 203
 204   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 205
 206   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 207
 208   libtest_threadset_thread_ready_and_wait( pts );
 209
 210   while( lfds710_freelist_pop(tpts->fs, &fe, &tpts->psts) )
 211   {
 212     te = LFDS710_FREELIST_GET_VALUE_FROM_ELEMENT( *fe );
 213     te->popped_flag = RAISED;
 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