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 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
prev sibling next sibling 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=

 flagged one is already removed.

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=

 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 next sibling parent 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
prev sibling 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