Subj : Re: atomic operations api added to AppCore...
To   : comp.programming.threads
From : Ronald Landheer-Cieslak
Date : Thu Feb 24 2005 01:09 pm

SenderX wrote:

>>Basically, you need *a* memory management system for this, but you could 
>>do it with a 32-bit CAS and hazard pointers without too much trouble: the 
>>hazard pointers would be necessary only to make sure you don't re-use a 
>>node while you shouldn't.
>>The way I'm implementing it now limits the deque to 32768 (2^15) nodes, 
>>which should be enough for most purposes: I allocate pointers for the 
>>nodes when the deque is first allocated in a simple, fixed-size array and 
>>keep the status (l,r,s) in a 32-bit structure containing a 15-bit index 
>>for both the left and right node (hence the limit of 32768 nodes) - the 
>>index points in the array allocated in the beginning - and the status on 
>>two bits.
>>The nodes are allocated as needed and placed in the array using a first 
>>CAS(NULL, &new_node, nodes[n]). For freeing a node, I do an atomic_swap to 
>>get the node and set nodes[n] to NULL, then use SMR to free the node.
> 
> 
> That will do it. I was wondering about something... How do you avoid aba in 
> your smr_hptr_free_list_deq/smr_hptr_free_list_enq functions?
There is no ABA as the memory is never freed and can only be used for
hazard pointers.

Deq-ing a hazard pointer set from the queue of "available" hazard
pointers is atomic:
    119 // the logic here should be much simpler that that of smr_hptr
    119 _free_list_enq: we
    120 // simply try to obtain a node from the free list and keep try
    120 ing until our CAS
    121 // works.
    122 static hptr_local_data_t * smr_hptr_free_list_deq(void)
    123 {
    124         hptr_local_data_t * retval;
    125         hptr_local_data_t * next;
    126
    127         do
    128         {
    129                 retval = smr_global_data->free;
    130                 next = retval->next;
    131         } while (compare_and_exchange_ptr(&retval, &(smr_globa
    131 l_data->free), next) != 0);
    132
    133         // we now have ownership of retval.
    134         retval->next = NULL;
    135         retval->flag = 0;
    136
    137         return retval;
    138 }
The CAS on line 131 moves the head of the queue to the node next to the
one we want to allocate. If it fails, that means our node was already
allocated (which might mean the contents of our next was wrong, but as
we don't set it to NULL until it is really ours, that doesn't really
matter).

In smr_hptr_free_list_enq, we already have exclusive ownership of the
node in DATA, so we could just take the head of the current queue, use
it as our next pointer and try to replace the head with what we found.
Apparently, though, for some reason I don't recall, I wanted the thing
to be FIFO, so I enqueue the node at the end. I really don't remember
why - I guess I'll just simplify it to:

    120 static void smr_hptr_free_list_enq(hptr_local_data_t * data)
    121 {
    122         hptr_local_data_t * exp;
    123
    124         for (i = 0; i < smr_global_data->k; i++)
    125                 data->hp[i] = NULL;
    126         data->flag = 1;
    127         data->next = NULL;
    128
    129         exp = NULL;
    130         while (compare_and_exchange_ptr(&exp, &(smr_global_dat
    130 a->free), data) != 0)
    131         {
    132                 data->next = exp;
    133         }
    134 }

HTH

rlc

.