2 #include "lfds710_freelist_internal.h"
8 /****************************************************************************/
9 void lfds710_freelist_push( struct lfds710_freelist_state *fs,
10 struct lfds710_freelist_element *fe,
11 struct lfds710_prng_st_state *psts )
17 backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE,
18 elimination_array_index,
22 struct lfds710_freelist_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_DOUBLE_POINTER)
24 *volatile original_top[PAC_SIZE];
26 LFDS710_PAL_ASSERT( fs != NULL );
27 LFDS710_PAL_ASSERT( fe != NULL );
28 // TRD : psts can be NULL
30 LFDS710_MISC_BARRIER_LOAD;
32 if( fs->elimination_array_size_in_elements > 0 )
36 LFDS710_PRNG_ST_GENERATE( *psts, random_value );
37 elimination_array_index = ( random_value & (fs->elimination_array_size_in_elements-1) );
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) );
46 // TRD : full scan of one cache line, max pointers per cache line
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 )
51 LFDS710_PAL_ATOMIC_EXCHANGE( &fs->elimination_array[elimination_array_index][loop], fe, struct lfds710_freelist_element * );
57 new_top[POINTER] = fe;
59 original_top[COUNTER] = fs->top[COUNTER];
60 original_top[POINTER] = fs->top[POINTER];
64 fe->next = original_top[POINTER];
65 LFDS710_MISC_BARRIER_STORE;
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 );
71 LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( fs->push_backoff, backoff_iteration );
75 LFDS710_BACKOFF_AUTOTUNE( fs->push_backoff, backoff_iteration );
84 /****************************************************************************/
85 void lfds710_freelist_internal_push_without_ea( struct lfds710_freelist_state *fs,
86 struct lfds710_freelist_element *fe )
92 backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE;
94 struct lfds710_freelist_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_DOUBLE_POINTER)
96 *volatile original_top[PAC_SIZE];
98 LFDS710_PAL_ASSERT( fs != NULL );
99 LFDS710_PAL_ASSERT( fe != NULL );
101 new_top[POINTER] = fe;
103 original_top[COUNTER] = fs->top[COUNTER];
104 original_top[POINTER] = fs->top[POINTER];
108 fe->next = original_top[POINTER];
109 LFDS710_MISC_BARRIER_STORE;
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 );
115 LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( fs->push_backoff, backoff_iteration );
117 while( result == 0 );
119 LFDS710_BACKOFF_AUTOTUNE( fs->push_backoff, backoff_iteration );