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

   1 /***** includes *****/
   2 #include "libtest_tests_internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds710_hash_a_element
   8     hae;
   9
  10   lfds710_pal_uint_t
  11     datum,
  12     key;
  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_hash_a_state
  24     *has;
  25
  26   struct test_element
  27     *element_array;
  28 };
  29
  30 /***** private prototypes *****/
  31 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state );
  32 static int key_compare_function( void const *new_key, void const *existing_key );
  33 static void key_hash_function( void const *key, lfds710_pal_uint_t *hash );
  34
  35
  36
  37
  38
  39 /****************************************************************************/
  40 void libtest_tests_hash_a_random_adds_fail_on_existing( 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_per_thread,
  45     number_elements_total,
  46     number_logical_processors,
  47     offset,
  48     temp,
  49     value;
  50
  51   struct lfds710_hash_a_element
  52     *hae;
  53
  54   struct lfds710_hash_a_state
  55     has;
  56
  57   struct lfds710_list_asu_element
  58     *lasue = NULL;
  59
  60   struct lfds710_btree_au_state
  61     *baus;
  62
  63   struct lfds710_prng_state
  64     ps;
  65
  66   struct lfds710_misc_validation_info
  67     vi;
  68
  69   struct libtest_logical_processor
  70     *lp;
  71
  72   struct libtest_threadset_per_thread_state
  73     *pts;
  74
  75   struct libtest_threadset_state
  76     ts;
  77
  78   struct test_element
  79     *element_array;
  80
  81   struct test_per_thread_state
  82     *tpts;
  83
  84   LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
  85   LFDS710_PAL_ASSERT( ms != NULL );
  86   LFDS710_PAL_ASSERT( dvs != NULL );
  87
  88   /* TRD : we create a single hash_a
  89            we generate 100k elements per thread (with one thread per logical processor) in an array
  90            each element is unique
  91            we randomly sort the elements
  92            then each thread loops, adds those elements into the hash_a
  93            we check that each datum inserts okay - failure will occur on non-unique data, i.e. two identical keys
  94            we should have no failures
  95            we then call the hash_a validation function
  96            then using the hash_a get() we check all the elements we added are present
  97   */
  98
  99   *dvs = LFDS710_MISC_VALIDITY_VALID;
 100
 101   // TRD : allocate
 102   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 103   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 104   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 105   baus = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct lfds710_btree_au_state) * 1000, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 106   element_array = libshared_memory_alloc_largest_possible_array_from_unknown_node( ms, sizeof(struct test_element), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES, &number_elements_total );
 107
 108   // TRD : for correct rounding, for later code
 109   number_elements_per_thread = number_elements_total / number_logical_processors;
 110   number_elements_total = number_elements_per_thread * number_logical_processors;
 111
 112   lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
 113
 114   lfds710_hash_a_init_valid_on_current_logical_core( &has, baus, 1000, key_compare_function, key_hash_function, LFDS710_HASH_A_EXISTING_KEY_FAIL, NULL );
 115
 116   // TRD : created an ordered list of unique numbers
 117   for( loop = 0 ; loop < number_elements_total ; loop++ )
 118   {
 119     (element_array+loop)->key = loop;
 120     // TRD : + number_elements just to make it different to the key
 121     (element_array+loop)->datum = loop + number_elements_total;
 122   }
 123
 124   // TRD : now randomize them
 125   for( loop = 0 ; loop < number_elements_total ; loop++ )
 126   {
 127     LFDS710_PRNG_GENERATE( ps, offset );
 128     offset %= number_elements_total;
 129     temp = (element_array + offset)->key;
 130     (element_array + offset)->key = (element_array + loop)->key;
 131     (element_array + loop)->key = temp;
 132   }
 133
 134   // TRD : get the threads ready
 135   libtest_threadset_init( &ts, NULL );
 136
 137   loop = 0;
 138
 139   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
 140   {
 141     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 142     (tpts+loop)->has = &has;
 143     (tpts+loop)->element_array = element_array + number_elements_per_thread*loop;
 144     (tpts+loop)->error_flag = LOWERED;
 145     (tpts+loop)->number_elements_per_thread = number_elements_per_thread;
 146     libtest_threadset_add_thread( &ts, &pts[loop], lp, thread_adding, &tpts[loop] );
 147     loop++;
 148   }
 149
 150   LFDS710_MISC_BARRIER_STORE;
 151
 152   lfds710_misc_force_store();
 153
 154   // TRD : run the test
 155   libtest_threadset_run( &ts );
 156
 157   libtest_threadset_cleanup( &ts );
 158
 159   // TRD : validate
 160   LFDS710_MISC_BARRIER_LOAD;
 161
 162   // TRD : now for validation
 163   vi.min_elements = vi.max_elements = number_elements_total;
 164   lfds710_hash_a_query( &has, LFDS710_HASH_A_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) dvs );
 165
 166   /* TRD : now we attempt to lfds710_hash_a_get_by_key() for every element in number_array
 167            any failure to find is an error
 168            we also check we've obtained the correct element
 169   */
 170
 171   for( loop = 0 ; *dvs == LFDS710_MISC_VALIDITY_VALID and loop < number_elements_total ; loop++ )
 172     if( 0 == lfds710_hash_a_get_by_key(&has, NULL, NULL, (void *) (tpts->element_array+loop)->key, &hae) )
 173       *dvs = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 174     else
 175     {
 176       value = (lfds710_pal_uint_t) LFDS710_HASH_A_GET_VALUE_FROM_ELEMENT( *hae );
 177       if( (tpts->element_array+loop)->datum != value )
 178         *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 179     }
 180
 181   // TRD : just check error_flags weren't raised
 182   if( *dvs == LFDS710_MISC_VALIDITY_VALID )
 183     for( loop = 0 ; loop < number_logical_processors ; loop++ )
 184       if( (tpts+loop)->error_flag == RAISED )
 185         *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 186
 187   // TRD : cleanup
 188   lfds710_hash_a_cleanup( &has, NULL );
 189
 190   return;
 191 }
 192
 193
 194
 195
 196
 197 /****************************************************************************/
 198 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state )
 199 {
 200   enum lfds710_hash_a_insert_result
 201     apr;
 202
 203   lfds710_pal_uint_t
 204     index = 0;
 205
 206   struct test_per_thread_state
 207     *tpts;
 208
 209   struct libtest_threadset_per_thread_state
 210     *pts;
 211
 212   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 213
 214   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 215
 216   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 217
 218   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 219
 220   libtest_threadset_thread_ready_and_wait( pts );
 221
 222   while( index < tpts->number_elements_per_thread )
 223   {
 224     LFDS710_HASH_A_SET_KEY_IN_ELEMENT( (tpts->element_array+index)->hae, (tpts->element_array+index)->key );
 225     LFDS710_HASH_A_SET_VALUE_IN_ELEMENT( (tpts->element_array+index)->hae, (tpts->element_array+index)->datum );
 226     apr = lfds710_hash_a_insert( tpts->has, &(tpts->element_array+index)->hae, NULL );
 227
 228     if( apr == LFDS710_HASH_A_PUT_RESULT_FAILURE_EXISTING_KEY )
 229       tpts->error_flag = RAISED;
 230
 231     index++;
 232   }
 233
 234   LFDS710_MISC_BARRIER_STORE;
 235
 236   lfds710_misc_force_store();
 237
 238   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 239 }
 240
 241
 242
 243
 244
 245 /****************************************************************************/
 246 #pragma warning( disable : 4100 )
 247
 248 static int key_compare_function( void const *new_key, void const *existing_key )
 249 {
 250   int
 251     cr = 0;
 252
 253   // TRD : new_key can be NULL (i.e. 0)
 254   // TRD : existing_key can be NULL (i.e. 0)
 255
 256   if( (lfds710_pal_uint_t) new_key < (lfds710_pal_uint_t) existing_key )
 257     cr = -1;
 258
 259   if( (lfds710_pal_uint_t) new_key > (lfds710_pal_uint_t) existing_key )
 260     cr = 1;
 261
 262   return cr;
 263 }
 264
 265 #pragma warning( default : 4100 )
 266
 267
 268
 269
 270
 271 /****************************************************************************/
 272 #pragma warning( disable : 4100 )
 273
 274 static void key_hash_function( void const *key, lfds710_pal_uint_t *hash )
 275 {
 276   // TRD : key can be NULL
 277   LFDS710_PAL_ASSERT( hash != NULL );
 278
 279   *hash = 0;
 280
 281   /* TRD : this function iterates over the user data
 282            and we are using the void pointer *as* key data
 283            so here we need to pass in the addy of key
 284   */
 285
 286   LFDS710_HASH_A_HASH_FUNCTION( (void *) &key, sizeof(lfds710_pal_uint_t), *hash );
 287
 288   return;
 289 }
 290
 291 #pragma warning( default : 4100 )
 292