Subj : Re: atomic operations api added to AppCore...
To   : comp.programming.threads
From : Ronald Landheer-Cieslak
Date : Fri Feb 25 2005 08:23 am

Ronald Landheer-Cieslak wrote:

> 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;
Oops: these should be atomic_set_ptr(&(data->hp[i]), NULL);: some other
thread might be reading.
>     126         data->flag = 1;
Not really a problem here as its boolean anyway...
>     127         data->next = NULL;
but this one should still be atomic..

>     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
rlc

.