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_with_cursor.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   enum flag
  18     error_flag;
  19
  20   lfds710_pal_uint_t
  21     number_elements_per_thread;
  22
  23   struct lfds710_list_aso_state
  24     *lasos;
  25
  26   struct test_element
  27     *element_array;
  28 };
  29
  30 /***** private prototypes *****/
  31 static int new_ordered_with_cursor_compare_function( void const *value_new, void const *value_in_list );
  32 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION new_ordered_with_cursor_insert_thread( void *libtest_threadset_per_thread_state );
  33 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION new_ordered_with_cursor_cursor_thread( void *libtest_threadset_per_thread_state );
  34
  35
  36
  37
  38
  39 /****************************************************************************/
  40 void libtest_tests_list_aso_new_ordered_with_cursor( struct lfds710_list_asu_state *list_of_logical_processors, struct libshared_memory_state *ms, enum lfds710_misc_validity *dvs )
  41 {
  42   lfds710_pal_uint_t
  43     loop,
  44     number_elements,
  45     number_elements_per_thread,
  46     number_elements_total,
  47     number_logical_processors,
  48     offset,
  49     temp;
  50
  51   struct lfds710_list_aso_state
  52     lasos;
  53
  54   struct lfds710_list_asu_element
  55     *lasue = NULL;
  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
  75   struct test_per_thread_state
  76     *tpts;
  77
  78   LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
  79   LFDS710_PAL_ASSERT( ms != NULL );
  80   LFDS710_PAL_ASSERT( dvs != NULL );
  81
  82   /* TRD : run two threads per logical processor
  83
  84            the test runs for 10 seconds
  85
  86            the first thread loops over a pre-set list of random numbers
  87            continually adding them using ordered insert
  88
  89            the second thread keeps iterating over the list, checking that
  90            each element is larger than its predecessor
  91   */
  92
  93   *dvs = LFDS710_MISC_VALIDITY_VALID;
  94
  95   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
  96   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors * 2, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  97   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 );
  98   element_array = libshared_memory_alloc_largest_possible_array_from_unknown_node( ms, sizeof(struct test_element), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES, &number_elements );
  99
 100   number_elements_per_thread = number_elements / number_logical_processors;
 101
 102   lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
 103
 104   lfds710_list_aso_init_valid_on_current_logical_core( &lasos, new_ordered_with_cursor_compare_function, LFDS710_LIST_ASO_INSERT_RESULT_FAILURE_EXISTING_KEY, NULL );
 105
 106   /* TRD : create randomly ordered number array with unique elements
 107
 108            unique isn't necessary - the list will sort anyway - but
 109            it permits slightly better validation
 110   */
 111
 112   // TRD : or the test takes a looooooong time...
 113   if( number_elements_per_thread > 1000 )
 114     number_elements_per_thread = 1000;
 115
 116   number_elements_total = number_elements_per_thread * number_logical_processors;
 117
 118   for( loop = 0 ; loop < number_elements_total ; loop++ )
 119     (element_array+loop)->element_number = loop;
 120
 121   for( loop = 0 ; loop < number_elements_total ; loop++ )
 122   {
 123     LFDS710_PRNG_GENERATE( ps, offset );
 124     offset %= number_elements_total;
 125     temp = (element_array + offset)->element_number;
 126     (element_array + offset)->element_number = (element_array + loop)->element_number;
 127     (element_array + loop)->element_number = temp;
 128   }
 129
 130   // TRD : get the threads ready
 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 : the insert threads
 140     (tpts+loop)->lasos = &lasos;
 141     (tpts+loop)->element_array = element_array + number_elements_per_thread*loop;
 142     (tpts+loop)->error_flag = LOWERED;
 143     (tpts+loop)->number_elements_per_thread = number_elements_per_thread;
 144     libtest_threadset_add_thread( &ts, &pts[loop], lp, new_ordered_with_cursor_insert_thread, &tpts[loop] );
 145
 146     // TRD : the cursor threads
 147     (tpts+loop+number_logical_processors)->lasos = &lasos;
 148     (tpts+loop+number_logical_processors)->element_array = NULL;
 149     (tpts+loop+number_logical_processors)->error_flag = LOWERED;
 150     libtest_threadset_add_thread( &ts, &pts[loop+number_logical_processors], lp, new_ordered_with_cursor_cursor_thread, &tpts[loop+number_logical_processors] );
 151
 152     loop++;
 153   }
 154
 155   LFDS710_MISC_BARRIER_STORE;
 156
 157   lfds710_misc_force_store();
 158
 159   libtest_threadset_run( &ts );
 160
 161   libtest_threadset_cleanup( &ts );
 162
 163   /* TRD : validate the resultant list
 164
 165            the cursor threads were checking for orderedness
 166            if that failed, they raise their error_flag
 167            so validate the list, then check error_flags
 168   */
 169
 170   LFDS710_MISC_BARRIER_LOAD;
 171
 172   vi.min_elements = vi.max_elements = number_elements_total;
 173
 174   lfds710_list_aso_query( &lasos, LFDS710_LIST_ASO_QUERY_SINGLETHREADED_VALIDATE, &vi, dvs );
 175
 176   if( *dvs == LFDS710_MISC_VALIDITY_VALID )
 177     for( loop = number_logical_processors ; loop < number_logical_processors * 2 ; loop++ )
 178       if( (tpts+loop)->error_flag == RAISED )
 179         *dvs = LFDS710_MISC_VALIDITY_INVALID_ORDER;
 180
 181   lfds710_list_aso_cleanup( &lasos, NULL );
 182
 183   return;
 184 }
 185
 186
 187
 188
 189
 190 /****************************************************************************/
 191 #pragma warning( disable : 4100 )
 192
 193 static int new_ordered_with_cursor_compare_function( void const *value_new, void const *value_in_list )
 194 {
 195   int
 196     cr = 0;
 197
 198   struct test_element
 199     *e1,
 200     *e2;
 201
 202   // TRD : value_new can be any value in its range
 203   // TRD : value_in_list can be any value in its range
 204
 205   e1 = (struct test_element *) value_new;
 206   e2 = (struct test_element *) value_in_list;
 207
 208   if( e1->element_number < e2->element_number )
 209     cr = -1;
 210
 211   if( e1->element_number > e2->element_number )
 212     cr = 1;
 213
 214   return cr;
 215 }
 216
 217 #pragma warning( default : 4100 )
 218
 219
 220
 221
 222
 223 /****************************************************************************/
 224 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION new_ordered_with_cursor_insert_thread( void *libtest_threadset_per_thread_state )
 225 {
 226   lfds710_pal_uint_t
 227     loop;
 228
 229   struct libtest_threadset_per_thread_state
 230     *pts;
 231
 232   struct test_per_thread_state
 233     *tpts;
 234
 235   LFDS710_MISC_BARRIER_LOAD;
 236
 237   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 238
 239   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 240   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 241
 242   libtest_threadset_thread_ready_and_wait( pts );
 243
 244   for( loop = 0 ; loop < tpts->number_elements_per_thread ; loop++ )
 245   {
 246     LFDS710_LIST_ASO_SET_KEY_IN_ELEMENT( (tpts->element_array+loop)->lasoe, tpts->element_array+loop );
 247     LFDS710_LIST_ASO_SET_VALUE_IN_ELEMENT( (tpts->element_array+loop)->lasoe, tpts->element_array+loop );
 248     lfds710_list_aso_insert( tpts->lasos, &(tpts->element_array+loop)->lasoe, NULL );
 249   }
 250
 251   LFDS710_MISC_BARRIER_STORE;
 252
 253   lfds710_misc_force_store();
 254
 255   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 256 }
 257
 258
 259
 260
 261
 262 /****************************************************************************/
 263 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION new_ordered_with_cursor_cursor_thread( void *libtest_threadset_per_thread_state )
 264 {
 265   lfds710_pal_uint_t
 266     prev_element_number;
 267
 268   lfds710_pal_uint_t
 269     time_loop = 0;
 270
 271   struct lfds710_list_aso_element
 272     *lasoe;
 273
 274   struct test_element
 275     *element;
 276
 277   struct libtest_threadset_per_thread_state
 278     *pts;
 279
 280   struct test_per_thread_state
 281     *tpts;
 282
 283   time_t
 284     current_time,
 285     start_time;
 286
 287   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 288
 289   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 290
 291   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 292   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 293
 294   libtest_threadset_thread_ready_and_wait( pts );
 295
 296   current_time = start_time = time( NULL );
 297
 298   while( current_time < start_time + TEST_DURATION_IN_SECONDS )
 299   {
 300     prev_element_number = 0;
 301
 302     lasoe = LFDS710_LIST_ASO_GET_START( *tpts->lasos );
 303
 304     // TRD : we may get start before any element has been added to the list
 305     if( lasoe == NULL )
 306       continue;
 307
 308     element = LFDS710_LIST_ASO_GET_VALUE_FROM_ELEMENT( *lasoe );
 309
 310     if( element->element_number < prev_element_number )
 311       tpts->error_flag = RAISED;
 312
 313     prev_element_number = element->element_number;
 314
 315     lasoe = LFDS710_LIST_ASO_GET_NEXT( *lasoe );
 316
 317     while( lasoe != NULL )
 318     {
 319       element = LFDS710_LIST_ASO_GET_VALUE_FROM_ELEMENT( *lasoe );
 320
 321       if( element->element_number <= prev_element_number )
 322         tpts->error_flag = RAISED;
 323
 324       prev_element_number = element->element_number;
 325
 326       lasoe = LFDS710_LIST_ASO_GET_NEXT( *lasoe );
 327     }
 328
 329     if( time_loop++ == REDUCED_TIME_LOOP_COUNT )
 330     {
 331       time_loop = 0;
 332       time( &current_time );
 333     }
 334   }
 335
 336   LFDS710_MISC_BARRIER_STORE;
 337
 338   lfds710_misc_force_store();
 339
 340   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 341 }
 342