pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/test_and_benchmark/libbenchmark/src/libbenchmark_benchmarks_freelist_push1_then_pop1/libbenchmark_benchmarks_freelist_liblfds700_lockfree_push1_then_pop1.c

   1 /***** includes *****/
   2 #include "libbenchmark_benchmarks_freelist_internal.h"
   3
   4 /***** structs *****/
   5 struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_per_thread_benchmark_state
   6 {
   7   lfds710_pal_uint_t
   8     operation_count;
   9 };
  10
  11 struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_overall_benchmark_state
  12 {
  13   struct lfds700_freelist_state
  14     *fs;
  15 };
  16
  17
  18
  19
  20
  21 /****************************************************************************/
  22 void libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_init( struct libbenchmark_topology_state *ts,
  23                                                                           struct lfds710_list_aso_state *logical_processor_set,
  24                                                                           struct libshared_memory_state *ms,
  25                                                                           enum libbenchmark_topology_numa_mode numa_mode,
  26                                                                           struct libbenchmark_threadset_state *tsets )
  27 {
  28   enum flag
  29     finished_flag = LOWERED;
  30
  31   struct lfds700_misc_prng_state
  32     ps;
  33
  34   lfds710_pal_uint_t
  35     *fe_array_count,
  36     index = 0,
  37     loop,
  38     number_logical_processors,
  39     number_logical_processors_in_numa_node,
  40     number_numa_nodes,
  41     largest_number_logical_processors_in_numa_node = 0;
  42
  43   struct lfds710_list_asu_element
  44     *lasue = NULL,
  45     *lasue_lp = NULL;
  46
  47   struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_overall_benchmark_state
  48     *obs;
  49
  50   struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_per_thread_benchmark_state
  51     *ptbs;
  52
  53   struct lfds700_freelist_element
  54     *fe,
  55     **fe_array_pointers;
  56
  57   struct lfds700_freelist_state
  58     *fs = NULL;
  59
  60   struct libbenchmark_threadset_per_numa_state
  61     *pns,
  62     *largest_pns = NULL;
  63
  64   struct libbenchmark_threadset_per_thread_state
  65     *pts;
  66
  67   struct libbenchmark_topology_node_state
  68     *numa_node_for_lp;
  69
  70   LFDS710_PAL_ASSERT( ts != NULL );
  71   LFDS710_PAL_ASSERT( logical_processor_set != NULL );
  72   LFDS710_PAL_ASSERT( ms != NULL );
  73   // TRD : numa_mode can be any value in its range
  74   LFDS710_PAL_ASSERT( tsets != NULL );
  75
  76   lfds700_misc_prng_init( &ps );
  77
  78   obs = libshared_memory_alloc_from_most_free_space_node( ms, sizeof(struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_overall_benchmark_state), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  79
  80   libbenchmark_threadset_init( tsets, ts, logical_processor_set, ms, libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_thread, NULL );
  81
  82   switch( numa_mode )
  83   {
  84     case LIBBENCHMARK_TOPOLOGY_NUMA_MODE_SMP:
  85       lfds710_list_aso_query( logical_processor_set, LFDS710_LIST_ASO_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void *) &number_logical_processors );
  86       fs = libshared_memory_alloc_from_most_free_space_node( ms, sizeof(struct lfds700_freelist_state), LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
  87       lfds700_freelist_init_valid_on_current_logical_core( fs, NULL );
  88
  89       fe = libshared_memory_alloc_from_most_free_space_node( ms, sizeof(struct lfds710_freelist_element) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  90       for( loop = 0 ; loop < number_logical_processors ; loop++ )
  91         lfds700_freelist_push( fs, &fe[loop], &ps );
  92       while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_thread_states,lasue) )
  93       {
  94         pts = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
  95         ptbs = libshared_memory_alloc_from_most_free_space_node( ms, sizeof(struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_per_thread_benchmark_state), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  96         pts->users_per_thread_state = ptbs;
  97       }
  98     break;
  99
 100     case LIBBENCHMARK_TOPOLOGY_NUMA_MODE_NUMA:
 101       /* TRD : init the freelist from the NUMA node with most processors from the current set
 102                or, if equal threads, with lowest NUMA
 103                iterate over the NUMA node list
 104                for each NUMA node, allocate one freelist element per thread on that node
 105                and push those elements onto the freelist
 106
 107                the loop over the threads, and give each one the freelist state as it's user state
 108       */
 109
 110       while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_numa_states,lasue) )
 111       {
 112         pns = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 113
 114         lasue_lp = NULL;
 115         number_logical_processors_in_numa_node = 0;
 116
 117         while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_thread_states,lasue_lp) )
 118         {
 119           pts = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue_lp );
 120
 121           libbenchmark_topology_query( ts, LIBBENCHMARK_TOPOLOGY_QUERY_GET_NUMA_NODE_FOR_LOGICAL_PROCESSOR, pts->tns_lp, &numa_node_for_lp );
 122
 123           if( LIBBENCHMARK_TOPOLOGY_NODE_GET_NUMA_ID(*numa_node_for_lp) == pns->numa_node_id )
 124             number_logical_processors_in_numa_node++;
 125         }
 126
 127         if( number_logical_processors_in_numa_node > largest_number_logical_processors_in_numa_node )
 128           largest_pns = pns;
 129       }
 130
 131       fs = libshared_memory_alloc_from_specific_node( ms, largest_pns->numa_node_id, sizeof(struct lfds710_freelist_state), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 132       lfds700_freelist_init_valid_on_current_logical_core( fs, NULL );
 133
 134       /* TRD : now figure out how many elements are needed from each NUMA node
 135                allocate them all
 136                them push them interleaved, round-robin, to the freelist
 137       */
 138
 139       libbenchmark_topology_query( ts, LIBBENCHMARK_TOPOLOGY_QUERY_GET_NUMBER_OF_NODE_TYPE, (void *) (lfds710_pal_uint_t) LIBBENCHMARK_TOPOLOGY_NODE_TYPE_NUMA, (void *) &number_numa_nodes );
 140
 141       fe_array_pointers = libshared_memory_alloc_from_most_free_space_node( ms, sizeof(struct lfds710_freelist_element *) * number_numa_nodes, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 142       fe_array_count = libshared_memory_alloc_from_most_free_space_node( ms, sizeof(lfds710_pal_uint_t) * number_numa_nodes, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 143       for( loop = 0 ; loop < number_numa_nodes ; loop++ )
 144         fe_array_count[loop] = 0;
 145
 146       lasue = NULL;
 147
 148       while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_numa_states,lasue) )
 149       {
 150         pns = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 151
 152         /* TRD : for each NUMA node, figure out how many LPs in the current set are in that NUMA node
 153                  and allocate then the correct number of elements from this NUMA node (1 per LP)
 154         */
 155
 156         lasue_lp = NULL;
 157         number_logical_processors_in_numa_node = 0;
 158
 159         while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_thread_states,lasue_lp) )
 160         {
 161           pts = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue_lp );
 162
 163           libbenchmark_topology_query( ts, LIBBENCHMARK_TOPOLOGY_QUERY_GET_NUMA_NODE_FOR_LOGICAL_PROCESSOR, pts->tns_lp, &numa_node_for_lp );
 164
 165           if( LIBBENCHMARK_TOPOLOGY_NODE_GET_NUMA_ID(*numa_node_for_lp) == pns->numa_node_id )
 166             number_logical_processors_in_numa_node++;
 167         }
 168
 169         fe_array_count[index] = number_logical_processors_in_numa_node;
 170         fe_array_pointers[index] = libshared_memory_alloc_from_specific_node( ms, pns->numa_node_id, sizeof(struct lfds710_freelist_element) * fe_array_count[index], LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 171         index++;
 172       }
 173
 174       while( finished_flag == LOWERED )
 175       {
 176         for( loop = 0 ; loop < index ; loop++ )
 177           if( fe_array_count[loop] > 0 )
 178             lfds700_freelist_push( fs, &fe_array_pointers[loop][ fe_array_count[loop]-- ], &ps );
 179
 180         finished_flag = RAISED;
 181
 182         for( loop = 0 ; loop < index ; loop++ )
 183           if( fe_array_count[loop] > 0 )
 184             finished_flag = LOWERED;
 185       }
 186
 187       lasue = NULL;
 188
 189       while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_thread_states,lasue) )
 190       {
 191         pts = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 192         ptbs = libshared_memory_alloc_from_specific_node( ms, largest_pns->numa_node_id, sizeof(struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_per_thread_benchmark_state), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 193         pts->users_per_thread_state = ptbs;
 194       }
 195     break;
 196
 197     case LIBBENCHMARK_TOPOLOGY_NUMA_MODE_NUMA_BUT_NOT_USED:
 198       /* TRD : freelist state in the NUMA node with most threads from the current set
 199                or, if equal threads, with lowest NUMA
 200                all elements alloced from that node as well
 201
 202                SO much easier to figure out allocs than with NUMA OMG
 203                all of this code needs rewriting
 204                and the NUMA-but-not-used stuff is interesting but I don't think it carries its own weight
 205       */
 206
 207       while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_numa_states,lasue) )
 208       {
 209         pns = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 210
 211         lasue_lp = NULL;
 212         number_logical_processors_in_numa_node = 0;
 213
 214         while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_thread_states,lasue_lp) )
 215         {
 216           pts = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue_lp );
 217
 218           libbenchmark_topology_query( ts, LIBBENCHMARK_TOPOLOGY_QUERY_GET_NUMA_NODE_FOR_LOGICAL_PROCESSOR, pts->tns_lp, &numa_node_for_lp );
 219
 220           if( LIBBENCHMARK_TOPOLOGY_NODE_GET_NUMA_ID(*numa_node_for_lp) == pns->numa_node_id )
 221             number_logical_processors_in_numa_node++;
 222         }
 223
 224         if( number_logical_processors_in_numa_node > largest_number_logical_processors_in_numa_node )
 225           largest_pns = pns;
 226       }
 227
 228       lfds710_list_aso_query( logical_processor_set, LFDS710_LIST_ASO_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void *) &number_logical_processors );
 229       fs = libshared_memory_alloc_from_specific_node( ms, largest_pns->numa_node_id, sizeof(struct lfds710_freelist_state), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 230       lfds700_freelist_init_valid_on_current_logical_core( fs, NULL );
 231
 232       // TRD : fill the elimination array and have one element per thread in the freelist proper
 233       fe = libshared_memory_alloc_from_specific_node( ms, largest_pns->numa_node_id, sizeof(struct lfds710_freelist_element) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 234       for( loop = 0 ; loop < number_logical_processors ; loop++ )
 235         lfds700_freelist_push( fs, &fe[loop], &ps );
 236
 237       lasue = NULL;
 238
 239       while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_thread_states,lasue) )
 240       {
 241         pts = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 242         ptbs = libshared_memory_alloc_from_specific_node( ms, largest_pns->numa_node_id, sizeof(struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_per_thread_benchmark_state), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 243         pts->users_per_thread_state = ptbs;
 244       }
 245     break;
 246   }
 247
 248   obs->fs = fs;
 249   tsets->users_threadset_state = obs;
 250
 251   return;
 252 }
 253
 254
 255
 256
 257
 258 /****************************************************************************/
 259 libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_thread( void *libbenchmark_threadset_per_thread_state )
 260 {
 261   int long long unsigned
 262     current_time = 0,
 263     end_time,
 264     time_units_per_second;
 265
 266   lfds710_pal_uint_t
 267     operation_count = 0,
 268     time_loop = 0;
 269
 270   struct lfds700_misc_prng_state
 271     ps;
 272
 273   struct lfds700_freelist_state
 274     *fs;
 275
 276   struct lfds700_freelist_element
 277     *fe;
 278
 279   struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_overall_benchmark_state
 280     *obs;
 281
 282   struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_per_thread_benchmark_state
 283     *ptbs;
 284
 285   struct libbenchmark_threadset_per_thread_state
 286     *pts;
 287
 288   LFDS710_MISC_BARRIER_LOAD;
 289
 290   LFDS710_PAL_ASSERT( libbenchmark_threadset_per_thread_state != NULL );
 291
 292   pts = (struct libbenchmark_threadset_per_thread_state *) libbenchmark_threadset_per_thread_state;
 293
 294   ptbs = LIBBENCHMARK_THREADSET_PER_THREAD_STATE_GET_USERS_PER_THREAD_STATE( *pts );
 295   obs = LIBBENCHMARK_THREADSET_PER_THREAD_STATE_GET_USERS_OVERALL_STATE( *pts );
 296   fs = obs->fs;
 297
 298   lfds700_misc_prng_init( &ps );
 299
 300   LIBBENCHMARK_PAL_TIME_UNITS_PER_SECOND( &time_units_per_second );
 301
 302   libbenchmark_threadset_thread_ready_and_wait( pts );
 303
 304   LIBBENCHMARK_PAL_GET_HIGHRES_TIME( &current_time );
 305
 306   end_time = current_time + time_units_per_second * libbenchmark_globals_benchmark_duration_in_seconds;
 307
 308   while( current_time < end_time )
 309   {
 310     lfds700_freelist_pop( fs, &fe, &ps );
 311     lfds700_freelist_push( fs, fe, &ps );
 312     operation_count++;
 313
 314     if( time_loop++ == TIME_LOOP_COUNT )
 315     {
 316       time_loop = 0;
 317       LIBBENCHMARK_PAL_GET_HIGHRES_TIME( &current_time );
 318     }
 319   }
 320
 321   ptbs->operation_count = operation_count;
 322
 323   LFDS710_MISC_BARRIER_STORE;
 324
 325   lfds710_misc_force_store();
 326
 327   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 328 }
 329
 330
 331
 332
 333
 334 /****************************************************************************/
 335 void libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_cleanup( struct lfds710_list_aso_state *logical_processor_set,
 336                                                                              enum libbenchmark_topology_numa_mode numa_mode,
 337                                                                              struct libbenchmark_results_state *rs,
 338                                                                              struct libbenchmark_threadset_state *tsets )
 339 {
 340   struct lfds710_list_asu_element
 341     *lasue = NULL;
 342
 343   struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_overall_benchmark_state
 344     *obs;
 345
 346   struct libbenchmark_benchmark_freelist_liblfds700_lockfree_push1_pop1_per_thread_benchmark_state
 347     *ptbs;
 348
 349   struct libbenchmark_threadset_per_thread_state
 350     *pts;
 351
 352   LFDS710_PAL_ASSERT( logical_processor_set != NULL );
 353   // TRD : numa_mode can be any value in its range
 354   LFDS710_PAL_ASSERT( rs != NULL );
 355   LFDS710_PAL_ASSERT( tsets != NULL );
 356
 357   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(tsets->list_of_per_thread_states,lasue) )
 358   {
 359     pts = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 360
 361     ptbs = LIBBENCHMARK_THREADSET_PER_THREAD_STATE_GET_USERS_PER_THREAD_STATE( *pts );
 362
 363     libbenchmark_results_put_result( rs,
 364                                      LIBBENCHMARK_DATASTRUCTURE_ID_FREELIST,
 365                                      LIBBENCHMARK_BENCHMARK_ID_PUSH1_THEN_POP1,
 366                                      LIBBENCHMARK_LOCK_ID_LIBLFDS700_LOCKFREE,
 367                                      numa_mode,
 368                                      logical_processor_set,
 369                                      LIBBENCHMARK_TOPOLOGY_NODE_GET_LOGICAL_PROCESSOR_NUMBER( *pts->tns_lp ),
 370                                      LIBBENCHMARK_TOPOLOGY_NODE_GET_WINDOWS_GROUP_NUMBER( *pts->tns_lp ),
 371                                      ptbs->operation_count );
 372   }
 373
 374   obs = tsets->users_threadset_state;
 375
 376   lfds700_freelist_cleanup( obs->fs, NULL );
 377
 378   return;
 379 }
 380