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

   1 /***** includes *****/
   2 #include "libtest_tests_internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds710_list_aso_element
   8     lasoe;
   9
  10   lfds710_pal_uint_t
  11     element_number,
  12     thread_number;
  13 };
  14
  15 struct test_per_thread_state
  16 {
  17   lfds710_pal_uint_t
  18     number_elements_per_thread;
  19
  20   struct lfds710_list_aso_state
  21     *lasos;
  22
  23   struct test_element
  24     *element_array;
  25 };
  26
  27 /***** private prototypes *****/
  28 static int new_ordered_compare_function( void const *value_new, void const *value_in_list );
  29 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION new_ordered_thread( void *libtest_threadset_per_thread_state );
  30
  31
  32
  33
  34
  35 /****************************************************************************/
  36 void libtest_tests_list_aso_new_ordered( struct lfds710_list_asu_state *list_of_logical_processors, struct libshared_memory_state *ms, enum lfds710_misc_validity *dvs )
  37 {
  38   lfds710_pal_uint_t
  39     loop,
  40     expected_element_number,
  41     number_elements,
  42     number_elements_per_thread,
  43     number_elements_total,
  44     number_logical_processors,
  45     offset,
  46     temp;
  47
  48   struct lfds710_list_aso_element
  49     *lasoe = NULL;
  50
  51   struct lfds710_list_asu_element
  52     *lasue = NULL;
  53
  54   struct lfds710_list_aso_state
  55     lasos;
  56
  57   struct lfds710_prng_state
  58     ps;
  59
  60   struct lfds710_misc_validation_info
  61     vi;
  62
  63   struct libtest_logical_processor
  64     *lp;
  65
  66   struct libtest_threadset_per_thread_state
  67     *pts;
  68
  69   struct libtest_threadset_state
  70     ts;
  71
  72   struct test_element
  73     *element_array,
  74     *element;
  75
  76   struct test_per_thread_state
  77     *tpts;
  78
  79   LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
  80   LFDS710_PAL_ASSERT( ms != NULL );
  81   LFDS710_PAL_ASSERT( dvs != NULL );
  82
  83   /* TRD : run one thread per logical processor
  84            we have a single array of 10k elements per thread
  85            this is set to be randomly ordered (but with contigious numbers from 0 to n)
  86            we give 10k to each thread (a pointer into the array at the correct point)
  87            which then loops through that array
  88            calling lfds710_list_aso_insert_element_by_position( LFDS710_LIST_ASO_POSITION_ORDERED )
  89            verification should show list is sorted
  90   */
  91
  92   *dvs = LFDS710_MISC_VALIDITY_VALID;
  93
  94   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
  95   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  96   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  97   element_array = libshared_memory_alloc_largest_possible_array_from_unknown_node( ms, sizeof(struct test_element), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES, &number_elements );
  98
  99   number_elements_per_thread = number_elements / number_logical_processors;
 100
 101   lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
 102
 103   lfds710_list_aso_init_valid_on_current_logical_core( &lasos, new_ordered_compare_function, LFDS710_LIST_ASO_INSERT_RESULT_FAILURE_EXISTING_KEY, NULL );
 104
 105   /* TRD : create randomly ordered number array with unique elements
 106
 107            unique isn't necessary - the list will sort anyway - but
 108            it permits slightly better validation
 109   */
 110
 111   // TRD : or the test takes a looooooong time...
 112   if( number_elements_per_thread > 10000 )
 113     number_elements_per_thread = 10000;
 114
 115   number_elements_total = number_elements_per_thread * number_logical_processors;
 116
 117   for( loop = 0 ; loop < number_elements_total ; loop++ )
 118     (element_array+loop)->element_number = loop;
 119
 120   for( loop = 0 ; loop < number_elements_total ; loop++ )
 121   {
 122     LFDS710_PRNG_GENERATE( ps, offset );
 123     offset %= number_elements_total;
 124     temp = (element_array + offset)->element_number;
 125     (element_array + offset)->element_number = (element_array + loop)->element_number;
 126     (element_array + loop)->element_number = temp;
 127   }
 128
 129   // TRD : get the threads ready
 130   libtest_threadset_init( &ts, NULL );
 131
 132   loop = 0;
 133
 134   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
 135   {
 136     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 137     (tpts+loop)->lasos = &lasos;
 138     (tpts+loop)->element_array = element_array + (loop*number_elements_per_thread);
 139     (tpts+loop)->number_elements_per_thread = number_elements_per_thread;
 140     libtest_threadset_add_thread( &ts, &pts[loop], lp, new_ordered_thread, &tpts[loop] );
 141     loop++;
 142   }
 143
 144   LFDS710_MISC_BARRIER_STORE;
 145
 146   lfds710_misc_force_store();
 147
 148   // TRD : run the test
 149   libtest_threadset_run( &ts );
 150
 151   libtest_threadset_cleanup( &ts );
 152
 153   /* TRD : validate the resultant list
 154            iterate over the list
 155            we expect to find the list is sorted,
 156            which means that element_number will
 157            increment from zero
 158   */
 159
 160   LFDS710_MISC_BARRIER_LOAD;
 161
 162   vi.min_elements = vi.max_elements = number_elements_total;
 163
 164   lfds710_list_aso_query( &lasos, LFDS710_LIST_ASO_QUERY_SINGLETHREADED_VALIDATE, &vi, dvs );
 165
 166   if( *dvs == LFDS710_MISC_VALIDITY_VALID )
 167   {
 168     expected_element_number = 0;
 169
 170     // TRD : traverse the list and check combined_data_array matches
 171     while( *dvs == LFDS710_MISC_VALIDITY_VALID and LFDS710_LIST_ASO_GET_START_AND_THEN_NEXT(lasos, lasoe) )
 172     {
 173       element = LFDS710_LIST_ASO_GET_VALUE_FROM_ELEMENT( *lasoe );
 174
 175       if( element->element_number != expected_element_number++ )
 176         *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 177     }
 178   }
 179
 180   lfds710_list_aso_cleanup( &lasos, NULL );
 181
 182   return;
 183 }
 184
 185
 186
 187
 188
 189 /****************************************************************************/
 190 #pragma warning( disable : 4100 )
 191
 192 static int new_ordered_compare_function( void const *value_new, void const *value_in_list )
 193 {
 194   int
 195     cr = 0;
 196
 197   struct test_element
 198     *e1,
 199     *e2;
 200
 201   // TRD : value_new can be any value in its range
 202   // TRD : value_in_list can be any value in its range
 203
 204   e1 = (struct test_element *) value_new;
 205   e2 = (struct test_element *) value_in_list;
 206
 207   if( e1->element_number < e2->element_number )
 208     cr = -1;
 209
 210   if( e1->element_number > e2->element_number )
 211     cr = 1;
 212
 213   return cr;
 214 }
 215
 216 #pragma warning( default : 4100 )
 217
 218
 219
 220
 221
 222 /****************************************************************************/
 223 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION new_ordered_thread( void *libtest_threadset_per_thread_state )
 224 {
 225   lfds710_pal_uint_t
 226     loop;
 227
 228   struct libtest_threadset_per_thread_state
 229     *pts;
 230
 231   struct test_per_thread_state
 232     *tpts;
 233
 234   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 235
 236   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 237
 238   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 239   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 240
 241   libtest_threadset_thread_ready_and_wait( pts );
 242
 243   for( loop = 0 ; loop < tpts->number_elements_per_thread ; loop++ )
 244   {
 245     LFDS710_LIST_ASO_SET_KEY_IN_ELEMENT( (tpts->element_array+loop)->lasoe, tpts->element_array+loop );
 246     LFDS710_LIST_ASO_SET_VALUE_IN_ELEMENT( (tpts->element_array+loop)->lasoe, tpts->element_array+loop );
 247     lfds710_list_aso_insert( tpts->lasos, &(tpts->element_array+loop)->lasoe, NULL );
 248   }
 249
 250   LFDS710_MISC_BARRIER_STORE;
 251
 252   lfds710_misc_force_store();
 253
 254   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 255 }
 256