pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_freelist/lfds710_freelist_push.c

   1 /***** includes *****/
   2 #include "lfds710_freelist_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 void lfds710_freelist_push( struct lfds710_freelist_state *fs,
  10                             struct lfds710_freelist_element *fe,
  11                             struct lfds710_prng_st_state *psts )
  12 {
  13   char unsigned
  14     result;
  15
  16   lfds710_pal_uint_t
  17     backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE,
  18     elimination_array_index,
  19     loop,
  20     random_value;
  21
  22   struct lfds710_freelist_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_DOUBLE_POINTER)
  23     *new_top[PAC_SIZE],
  24     *volatile original_top[PAC_SIZE];
  25
  26   LFDS710_PAL_ASSERT( fs != NULL );
  27   LFDS710_PAL_ASSERT( fe != NULL );
  28   // TRD : psts can be NULL
  29
  30   LFDS710_MISC_BARRIER_LOAD;
  31
  32   if( fs->elimination_array_size_in_elements > 0 )
  33   {
  34     if( psts != NULL )
  35     {
  36       LFDS710_PRNG_ST_GENERATE( *psts, random_value );
  37       elimination_array_index = ( random_value & (fs->elimination_array_size_in_elements-1) );
  38     }
  39     else
  40     {
  41       elimination_array_index = (lfds710_pal_uint_t) fe;
  42       LFDS710_PRNG_ST_MIXING_FUNCTION( elimination_array_index );
  43       elimination_array_index = ( elimination_array_index & (fs->elimination_array_size_in_elements-1) );
  44     }
  45
  46     // TRD : full scan of one cache line, max pointers per cache line
  47
  48     for( loop = 0 ; loop < LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS ; loop++ )
  49       if( fs->elimination_array[elimination_array_index][loop] == NULL )
  50       {
  51         LFDS710_PAL_ATOMIC_EXCHANGE( &fs->elimination_array[elimination_array_index][loop], fe, struct lfds710_freelist_element * );
  52         if( fe == NULL )
  53           return;
  54       }
  55   }
  56
  57   new_top[POINTER] = fe;
  58
  59   original_top[COUNTER] = fs->top[COUNTER];
  60   original_top[POINTER] = fs->top[POINTER];
  61
  62   do
  63   {
  64     fe->next = original_top[POINTER];
  65     LFDS710_MISC_BARRIER_STORE;
  66
  67     new_top[COUNTER] = original_top[COUNTER] + 1;
  68     LFDS710_PAL_ATOMIC_DWCAS( fs->top, original_top, new_top, LFDS710_MISC_CAS_STRENGTH_WEAK, result );
  69
  70     if( result == 0 )
  71       LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( fs->push_backoff, backoff_iteration );
  72   }
  73   while( result == 0 );
  74
  75   LFDS710_BACKOFF_AUTOTUNE( fs->push_backoff, backoff_iteration );
  76
  77   return;
  78 }
  79
  80
  81
  82
  83
  84 /****************************************************************************/
  85 void lfds710_freelist_internal_push_without_ea( struct lfds710_freelist_state *fs,
  86                                                 struct lfds710_freelist_element *fe )
  87 {
  88   char unsigned
  89     result;
  90
  91   lfds710_pal_uint_t
  92     backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE;
  93
  94   struct lfds710_freelist_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_DOUBLE_POINTER)
  95     *new_top[PAC_SIZE],
  96     *volatile original_top[PAC_SIZE];
  97
  98   LFDS710_PAL_ASSERT( fs != NULL );
  99   LFDS710_PAL_ASSERT( fe != NULL );
 100
 101   new_top[POINTER] = fe;
 102
 103   original_top[COUNTER] = fs->top[COUNTER];
 104   original_top[POINTER] = fs->top[POINTER];
 105
 106   do
 107   {
 108     fe->next = original_top[POINTER];
 109     LFDS710_MISC_BARRIER_STORE;
 110
 111     new_top[COUNTER] = original_top[COUNTER] + 1;
 112     LFDS710_PAL_ATOMIC_DWCAS( fs->top, original_top, new_top, LFDS710_MISC_CAS_STRENGTH_WEAK, result );
 113
 114     if( result == 0 )
 115       LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( fs->push_backoff, backoff_iteration );
 116   }
 117   while( result == 0 );
 118
 119   LFDS710_BACKOFF_AUTOTUNE( fs->push_backoff, backoff_iteration );
 120
 121   return;
 122 }
 123