pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/test/src/test_lfds700_list_addonly_ordered_singlylinked_new_ordered_with_cursor.c

   1 /***** includes *****/
   2 #include "internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds700_list_aos_element
   8     laose;
   9
  10   lfds700_pal_uint_t
  11     element_number,
  12     thread_number;
  13 };
  14
  15 struct test_state
  16 {
  17   enum flag
  18     error_flag;
  19
  20   lfds700_pal_uint_t
  21     number_elements_per_thread;
  22
  23   struct lfds700_list_aos_state
  24     *laoss;
  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 test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_with_cursor_insert_thread( void *util_thread_starter_thread_state );
  33 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_with_cursor_cursor_thread( void *util_thread_starter_thread_state );
  34
  35
  36
  37
  38
  39 /****************************************************************************/
  40 void test_lfds700_list_aos_new_ordered_with_cursor( struct lfds700_list_asu_state *list_of_logical_processors, lfds700_pal_uint_t memory_in_megabytes )
  41 {
  42   enum lfds700_misc_validity
  43     dvs = LFDS700_MISC_VALIDITY_VALID;
  44
  45   lfds700_pal_uint_t
  46     loop,
  47     number_elements_per_thread,
  48     number_elements_total,
  49     number_logical_processors,
  50     offset,
  51     temp;
  52
  53   struct lfds700_list_aos_state
  54     laoss;
  55
  56   struct lfds700_list_asu_element
  57     *lasue = NULL;
  58
  59   struct lfds700_misc_prng_state
  60     ps;
  61
  62   struct lfds700_misc_validation_info
  63     vi;
  64
  65   struct test_pal_logical_processor
  66     *lp;
  67
  68   struct util_thread_starter_state
  69     *tts;
  70
  71   struct test_element
  72     *element_array;
  73
  74   struct test_state
  75     *ts;
  76
  77   test_pal_thread_state_t
  78     *thread_handles;
  79
  80   assert( list_of_logical_processors != NULL );
  81   // TRD : memory_in_megabytes can be any value in its range
  82
  83   /* TRD : run two threads per logical processor
  84
  85            the test runs for 10 seconds
  86
  87            the first thread loops over a pre-set list of random numbers
  88            continually adding them using ordered insert
  89
  90            the second thread keeps iterating over the list, checking that
  91            each element is larger than its predecessor
  92   */
  93
  94   internal_display_test_name( "New ordered with cursor (%d seconds)", TEST_DURATION_IN_SECONDS );
  95
  96   lfds700_misc_prng_init( &ps );
  97
  98   lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
  99
 100   lfds700_list_aos_init_valid_on_current_logical_core( &laoss, new_ordered_with_cursor_compare_function, LFDS700_LIST_AOS_INSERT_RESULT_FAILURE_EXISTING_KEY, NULL );
 101
 102   /* TRD : create randomly ordered number array with unique elements
 103
 104            unique isn't necessary - the list will sort anyway - but
 105            it permits slightly better validation
 106   */
 107
 108   number_elements_per_thread = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors );
 109
 110   // TRD : or the test takes a looooooong time...
 111   if( number_elements_per_thread > 1000 )
 112     number_elements_per_thread = 1000;
 113
 114   number_elements_total = number_elements_per_thread * number_logical_processors;
 115
 116   element_array = util_aligned_malloc( sizeof(struct test_element) * number_elements_total, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
 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     offset = LFDS700_MISC_PRNG_GENERATE( &ps );
 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   ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors * 2 );
 131
 132   // TRD : the insert threads
 133   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 134   {
 135     (ts+loop)->laoss = &laoss;
 136     (ts+loop)->element_array = element_array + number_elements_per_thread*loop;
 137     (ts+loop)->error_flag = LOWERED;
 138     (ts+loop)->number_elements_per_thread = number_elements_per_thread;
 139   }
 140
 141   // TRD : the cursor threads
 142   for( loop = number_logical_processors ; loop < number_logical_processors * 2 ; loop++ )
 143   {
 144     (ts+loop)->laoss = &laoss;
 145     (ts+loop)->element_array = NULL;
 146     (ts+loop)->error_flag = LOWERED;
 147   }
 148
 149   thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors * 2 );
 150
 151   util_thread_starter_new( &tts, number_logical_processors * 2 );
 152
 153   LFDS700_MISC_BARRIER_STORE;
 154
 155   lfds700_misc_force_store();
 156
 157   loop = 0;
 158
 159   while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
 160   {
 161     lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 162     util_thread_starter_start( tts, &thread_handles[loop], loop, lp, new_ordered_with_cursor_insert_thread, ts+loop );
 163     util_thread_starter_start( tts, &thread_handles[loop+number_logical_processors], loop+number_logical_processors, lp, new_ordered_with_cursor_cursor_thread, ts+loop+number_logical_processors );
 164     loop++;
 165   }
 166
 167   util_thread_starter_run( tts );
 168
 169   for( loop = 0 ; loop < number_logical_processors * 2 ; loop++ )
 170     test_pal_thread_wait( thread_handles[loop] );
 171
 172   util_thread_starter_delete( tts );
 173
 174   free( thread_handles );
 175
 176   /* TRD : validate the resultant list
 177
 178            the cursor threads were checking for orderedness
 179            if that failed, they raise their error_flag
 180            so validate the list, then check error_flags
 181   */
 182
 183   LFDS700_MISC_BARRIER_LOAD;
 184
 185   vi.min_elements = vi.max_elements = number_elements_total;
 186
 187   lfds700_list_aos_query( &laoss, LFDS700_LIST_AOS_QUERY_SINGLETHREADED_VALIDATE, &vi, &dvs );
 188
 189   if( dvs == LFDS700_MISC_VALIDITY_VALID )
 190     for( loop = number_logical_processors ; loop < number_logical_processors * 2 ; loop++ )
 191       if( (ts+loop)->error_flag == RAISED )
 192         dvs = LFDS700_MISC_VALIDITY_INVALID_ORDER;
 193
 194   lfds700_list_aos_cleanup( &laoss, NULL );
 195
 196   util_aligned_free( element_array );
 197
 198   free( ts );
 199
 200   internal_display_test_result( 1, "list_aos", dvs );
 201
 202   return;
 203 }
 204
 205
 206
 207
 208
 209 /****************************************************************************/
 210 #pragma warning( disable : 4100 )
 211
 212 static int new_ordered_with_cursor_compare_function( void const *value_new, void const *value_in_list )
 213 {
 214   int
 215     cr = 0;
 216
 217   struct test_element
 218     *e1,
 219     *e2;
 220
 221   // TRD : value_new can be any value in its range
 222   // TRD : value_in_list can be any value in its range
 223
 224   e1 = (struct test_element *) value_new;
 225   e2 = (struct test_element *) value_in_list;
 226
 227   if( e1->element_number < e2->element_number )
 228     cr = -1;
 229
 230   if( e1->element_number > e2->element_number )
 231     cr = 1;
 232
 233   return( cr );
 234 }
 235
 236 #pragma warning( default : 4100 )
 237
 238
 239
 240
 241
 242 /****************************************************************************/
 243 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_with_cursor_insert_thread( void *util_thread_starter_thread_state )
 244 {
 245   lfds700_pal_uint_t
 246     loop;
 247
 248   struct lfds700_misc_prng_state
 249     ps;
 250
 251   struct test_state
 252     *ts;
 253
 254   struct util_thread_starter_thread_state
 255     *tsts;
 256
 257   LFDS700_MISC_BARRIER_LOAD;
 258
 259   assert( util_thread_starter_thread_state != NULL );
 260
 261   tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
 262   ts = (struct test_state *) tsts->thread_user_state;
 263
 264   lfds700_misc_prng_init( &ps );
 265
 266   util_thread_starter_ready_and_wait( tsts );
 267
 268   for( loop = 0 ; loop < ts->number_elements_per_thread ; loop++ )
 269   {
 270     LFDS700_LIST_AOS_SET_KEY_IN_ELEMENT( (ts->element_array+loop)->laose, ts->element_array+loop );
 271     LFDS700_LIST_AOS_SET_VALUE_IN_ELEMENT( (ts->element_array+loop)->laose, ts->element_array+loop );
 272     lfds700_list_aos_insert( ts->laoss, &(ts->element_array+loop)->laose, NULL, &ps );
 273   }
 274
 275   LFDS700_MISC_BARRIER_STORE;
 276
 277   lfds700_misc_force_store();
 278
 279   return( (test_pal_thread_return_t) EXIT_SUCCESS );
 280 }
 281
 282
 283
 284
 285
 286 /****************************************************************************/
 287 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_with_cursor_cursor_thread( void *util_thread_starter_thread_state )
 288 {
 289   lfds700_pal_uint_t
 290     prev_element_number;
 291
 292   lfds700_pal_uint_t
 293     time_loop = 0;
 294
 295   struct lfds700_list_aos_element
 296     *laose;
 297
 298   struct test_element
 299     *element;
 300
 301   struct test_state
 302     *ts;
 303
 304   struct util_thread_starter_thread_state
 305     *tsts;
 306
 307   time_t
 308     current_time,
 309     start_time;
 310
 311   LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 312
 313   assert( util_thread_starter_thread_state != NULL );
 314
 315   tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
 316   ts = (struct test_state *) tsts->thread_user_state;
 317
 318   util_thread_starter_ready_and_wait( tsts );
 319
 320   current_time = start_time = time( NULL );
 321
 322   while( current_time < start_time + TEST_DURATION_IN_SECONDS )
 323   {
 324     prev_element_number = 0;
 325
 326     laose = LFDS700_LIST_AOS_GET_START( *ts->laoss );
 327
 328     // TRD : we may get start before any element has been added to the list
 329     if( laose == NULL )
 330       continue;
 331
 332     element = LFDS700_LIST_AOS_GET_VALUE_FROM_ELEMENT( *laose );
 333
 334     if( element->element_number < prev_element_number )
 335       ts->error_flag = RAISED;
 336
 337     prev_element_number = element->element_number;
 338
 339     laose = LFDS700_LIST_AOS_GET_NEXT( *laose );
 340
 341     while( laose != NULL )
 342     {
 343       element = LFDS700_LIST_AOS_GET_VALUE_FROM_ELEMENT( *laose );
 344
 345       if( element->element_number <= prev_element_number )
 346         ts->error_flag = RAISED;
 347
 348       prev_element_number = element->element_number;
 349
 350       laose = LFDS700_LIST_AOS_GET_NEXT( *laose );
 351     }
 352
 353     if( time_loop++ == REDUCED_TIME_LOOP_COUNT )
 354     {
 355       time_loop = 0;
 356       time( &current_time );
 357     }
 358   }
 359
 360   LFDS700_MISC_BARRIER_STORE;
 361
 362   lfds700_misc_force_store();
 363
 364   return( (test_pal_thread_return_t) EXIT_SUCCESS );
 365 }
 366