Skip to content

Instantly share code, notes, and snippets.

@atomictom
Created April 21, 2015 22:50
Show Gist options
  • Save atomictom/f545755386c63ee37ddd to your computer and use it in GitHub Desktop.
Save atomictom/f545755386c63ee37ddd to your computer and use it in GitHub Desktop.
/* Because bitset comprises 3 operations:
* 1. Read array[bitset_index] into 'temp'
* 2. Set bit (bit_index) on 'temp'
* 3. Write 'temp' into array[bitset_index]
* A thread running bitset can be preempted before it can write 'temp', during
* which time another thread has written 'array[bitset_index]', and 'temp' does
* not include the changes made by that thread. Thus, the preempted thread
* overwrites the changes made by the other thread when it executes step 3.
*
* To avoid this, I use the GCC extension '__sync_bool_compare_and_swap' which
* does an atomic compare and swap with 'oldval' (the initial value of
* array[bitset_index]) and 'newval' ('oldval' with the relevant bit set on it)
* and returns true if the operation succeeded and false if it doesn't.
*
* Thus, I just use it in a do while loop and keep trying the operation until
* it succeeds.
*/
void bitset(unsigned char * array, int index){
int newval;
int oldval;
int bitset_index = index / BITS_PER_INDEX;
int bit_index = index % BITS_PER_INDEX;
do{
oldval = array[bitset_index];
newval = oldval | (1 << (bit_index));
}while(!__sync_bool_compare_and_swap(&array[bitset_index], oldval, newval));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment