www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Hazard pointers needed with GC ?

reply "Martin Nowak" <dawg dawgfoto.de> writes:
I implemented a lock-free doubly linked list some time ago.
I omitted the use of hazard lists because flagging the lowest
bit would still make a valid pointer into the list node.
Afterwards I found that http://www.d-programming-language.org/garbage.html  
explicitly states:
   p = cast(void*)(cast(int)p | 1);  // error: undefined behavior

Is this really needed? Guess the current GC would work properly.

Also if a list node were
   Node(T)
   {
     ubyte[2] data;
     T           t;
   }
Than both a pointer to data[0] as well as one to data[1] are valid
and effectively hold the node.

martin
Dec 07 2011
next sibling parent reply deadalnix <deadalnix gmail.com> writes:
Le 07/12/2011 18:02, Martin Nowak a écrit :

 I implemented a lock-free doubly linked list some time ago.
 I omitted the use of hazard lists because flagging the lowest
 bit would still make a valid pointer into the list node.
 Afterwards I found that
 http://www.d-programming-language.org/garbage.html explicitly states:
 p = cast(void*)(cast(int)p | 1); // error: undefined behavior

 Is this really needed? Guess the current GC would work properly.

 Also if a list node were
 Node(T)
 {
 ubyte[2] data;
 T t;
 }
 Than both a pointer to data[0] as well as one to data[1] are valid
 and effectively hold the node.

 martin


When doing so, you should anyway have a local pointer to that data. So 
it will not be collected until you release that local pointer, when the 
flagged one is already removed.

Flagged pointer is a temporary state. It is usefull because falgging can 
be done as an atomic operation. But the flagged pointer is not here to 
stay. It is here to mention to others thread that an ongoing operation 
is concurently running.
Dec 07 2011
parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Wed, 07 Dec 2011 18:28:59 +0100, deadalnix <deadalnix gmail.com> wrot=
e:


 Le 07/12/2011 18:02, Martin Nowak a =C3=A9crit :

 I implemented a lock-free doubly linked list some time ago.
 I omitted the use of hazard lists because flagging the lowest
 bit would still make a valid pointer into the list node.
 Afterwards I found that
 http://www.d-programming-language.org/garbage.html explicitly states:=





 p =3D cast(void*)(cast(int)p | 1); // error: undefined behavior

 Is this really needed? Guess the current GC would work properly.

 Also if a list node were
 Node(T)
 {
 ubyte[2] data;
 T t;
 }
 Than both a pointer to data[0] as well as one to data[1] are valid
 and effectively hold the node.

 martin


 When doing so, you should anyway have a local pointer to that data. So=


  =


 it will not be collected until you release that local pointer, when th=


e  =


 flagged one is already removed.


That's exactly what a hazard pointer is used for.
Now the question is if the flagged pointer still points to
valid memory in the same object (union aliased), there should
be no need for thread local hazard pointers.


 Flagged pointer is a temporary state. It is usefull because falgging c=


an  =


 be done as an atomic operation. But the flagged pointer is not here to=


  =


 stay. It is here to mention to others thread that an ongoing operation=


  =


 is concurently running.
Dec 07 2011
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/07/2011 06:02 PM, Martin Nowak wrote:

 I implemented a lock-free doubly linked list some time ago.
 I omitted the use of hazard lists because flagging the lowest
 bit would still make a valid pointer into the list node.
 Afterwards I found that
 http://www.d-programming-language.org/garbage.html explicitly states:
 p = cast(void*)(cast(int)p | 1); // error: undefined behavior

 Is this really needed? Guess the current GC would work properly.

 Also if a list node were
 Node(T)
 {
 ubyte[2] data;
 T t;
 }
 Than both a pointer to data[0] as well as one to data[1] are valid
 and effectively hold the node.

 martin


TDPL suggests that using that kind of pointer flagging is sane. Maybe 
you can file a bug against the specification.
Dec 07 2011
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 12/7/2011 9:02 AM, Martin Nowak wrote:

 I implemented a lock-free doubly linked list some time ago.
 I omitted the use of hazard lists because flagging the lowest
 bit would still make a valid pointer into the list node.
 Afterwards I found that http://www.d-programming-language.org/garbage.html
 explicitly states:
 p = cast(void*)(cast(int)p | 1); // error: undefined behavior

 Is this really needed? Guess the current GC would work properly.

 Also if a list node were
 Node(T)
 {
 ubyte[2] data;
 T t;
 }
 Than both a pointer to data[0] as well as one to data[1] are valid
 and effectively hold the node.


If the GC runs a collection cycle while the pointer has that bit set, and 
setting the bit causes it to point past the allocated data, then it will not 
regard that data as being in use and will delete it.

An easy way to make it work right is to make sure that or'ing in the bit will 
not cause the pointer to point past the object.
Dec 07 2011
parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Wed, 07 Dec 2011 23:23:26 +0100, Walter Bright  
<newshound2 digitalmars.com> wrote:


 On 12/7/2011 9:02 AM, Martin Nowak wrote:

 I implemented a lock-free doubly linked list some time ago.
 I omitted the use of hazard lists because flagging the lowest
 bit would still make a valid pointer into the list node.
 Afterwards I found that  
 http://www.d-programming-language.org/garbage.html
 explicitly states:
 p = cast(void*)(cast(int)p | 1); // error: undefined behavior

 Is this really needed? Guess the current GC would work properly.

 Also if a list node were
 Node(T)
 {
 ubyte[2] data;
 T t;
 }
 Than both a pointer to data[0] as well as one to data[1] are valid
 and effectively hold the node.


 If the GC runs a collection cycle while the pointer has that bit set,  
 and setting the bit causes it to point past the allocated data, then it  
 will not regard that data as being in use and will delete it.

 An easy way to make it work right is to make sure that or'ing in the bit  
 will not cause the pointer to point past the object.


Nice, this really simplifies lock-free data structures.
Dec 07 2011