Re: My -short- lock-free sequencer class, I want to see your comments
This is a multi-part message in MIME format.
------=_NextPart_000_0016_01C90C39.8A108F20
Content-Type: text/plain;
charset="Utf-8"
Content-Transfer-Encoding: quoted-printable
Thanks Ulrich,
I just want to show the logic in its simplest form. I am not a C++ guru =
indeed. I updated the code as long as I understand what you mean. Before =
I put the updated code, I want to ask you a couple of questions about =
your comments:
You said : "...Further, your class is still default-constructible, =
copyable and assignable."
Do you mean that I should implement a copy constructor to handle =
assignment and copy?
You said : "InterlockedExchange() takes a pointer to a volatile LONG. =
While this is automatically added in a function call, it is still =
necessary in isInOrder()..."
All assignments to m_lRunningOrder are done by Interlocked manner. So, I =
think no visibilty issue would be introduced even though the variable is =
not volatile. Correct???
/////////////////////////////////////////////////////////////////////////=
////
class Sequencer
{
public:
explicit Sequencer (LONG lMaxSequence) :
m_lCurrentSequence (0),
m_lRunningOrder (0),
m_lMaxSequence (lMaxSequence)
{
}
// Returns next available sequence number. If the current sequence =
is equal to max sequence number then zero returns.
// Should be called before start an operation which need to be =
in-order
LONG getNextSequence ()
{
LONG lCurrentSequence, lNextSequence;
while (true)
{
InterlockedExchange (&lCurrentSequence, =
m_lCurrentSequence); // Make local copy of the variable.
lNextSequence = (lCurrentSequence == m_lMaxSequence =
? 0 : lCurrentSequence + 1); // Calculate next sequence number. If =
current sequence is equal to max then next sequence is zero.
// If another thread already changed the current sequence =
number then recalculate. Otherwise update the sequence number and return =
next sequence.
if (lCurrentSequence == InterlockedCompareExchange =
(&m_lCurrentSequence, lNextSequence, lCurrentSequence))
{
break;
}
}
return lNextSequence;
}
// When an operation is completed, this method should be called.
bool updateRunningOrder (const LONG lSequence)
{
if (isInOrder (lSequence)) // Allow only in-order operations.
{
// If properly used then the class guarantees that only =
one thread can be here at a time. So we can manuplate m_lRunnigOrder in =
thread-safe manner.
LONG lNewRunningOrder = (lSequence + 1) > =
m_lMaxSequence ? 0 : (lSequence + 1); // Next operation to complete. =
Again we circulate if we go beyond the max.
InterlockedExchange (&m_lRunningOrder, lNewRunningOrder);
return true;
}
return false;
}
bool isInOrder (const LONG lSequence) const
{
return (lSequence == m_lRunningOrder);
}
private:
Sequencer () {};
LONG m_lMaxSequence; // Sequence number limit to =
circulate.
LONG m_lCurrentSequence; // Current sequence value for =
starting operations.
volatile LONG m_lRunningOrder; // Next operation to be completed.
};
"Ulrich Eckhardt" <eckhardt@satorlaser.com> wrote in message =
news:bbjso5-44v.ln1@satorlaser.homedns.org...
Krat wrote:
Hi,
Recently I needed a sequencer for my IOCP based socket server and
developed one. I try to implement it in lock-free manner. Your =
comments
will bee appreciated.
The class is very small and all it do is to maintain two numbers in =
thread
safe manner. Before every WSARecv call I get next available sequence
number from sequencer and put that number into my PerIoContext =
object.
When a recv completion occured then I check the sequence number to =
decide
if the completion occured in order. So one of the two numbers
(m_lCurrentSequence) represents call sequence and the other
(m_lRunningOrder) represents completion sequence. Here is the class :
class Sequencer
{
public:
Sequencer (LONG lMaxSequence) : m_lCurrentSequence (0),
m_lRunningOrder
(0), m_lMaxSequence (lMaxSequence)
{
}
Single-argument constructor that is not declared 'explicit' allows =
implicit
conversions, which are usually bad. Further, your class is still
default-constructible, copyable and assignable.
LONG getNextSequence ()
{
LONG lCurrentSequence, lNextSequence;
while (true)
{
InterlockedExchange (&lCurrentSequence,
m_lCurrentSequence); lNextSequence = =
(lCurrentSequence ==
m_lMaxSequence ? 0 :
lCurrentSequence + 1);
if (lCurrentSequence == InterlockedCompareExchange
(&m_lCurrentSequence, lNextSequence, lCurrentSequence))
{
break;
}
}
return lNextSequence;
}
Inconsistent formatting, making it harder to understand what's going =
on.
Further, the whole code is undocumented. Documenting the design of =
code
often leads to the discovery of logic errors and allows maintenance by
others.
bool isInOrder (const LONG lSequence)
{
return (lSequence == m_lRunningOrder);
}
Should be const.
bool updateRunningOrder (const LONG lSequence)
{
if (isInOrder (lSequence))
{
// Safe region...
LONG lNewRunningOrder = (lSequence + 1) > m_lMaxSequence =
? 0 :
(lSequence + 1);
InterlockedExchange (&m_lRunningOrder, lNewRunningOrder);
return true;
}
return false;
}
private:
LONG m_lMaxSequence;
LONG m_lCurrentSequence;
LONG m_lRunningOrder;
};
InterlockedExchange() takes a pointer to a volatile LONG. While this =
is
automatically added in a function call, it is still necessary in
isInOrder(). Why? Simple reason: the compiler implements read-accesses =
to a
volatile in a way similar to the Interlocked*() functions. In fact, a
simple InterlockedRead() function is missing from that API.
Uli
--
C++ FAQ: http://parashift.com/c++-faq-lite
Sator Laser GmbH
Gesch=C3=A4ftsf=C3=BChrer: Thorsten F=C3=B6cking, Amtsgericht Hamburg =
HR B62 932
------=_NextPart_000_0016_01C90C39.8A108F20
Content-Type: text/html;
charset="Utf-8"
Content-Transfer-Encoding: quoted-printable
=EF=BB=BF<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<META content="MSHTML 6.00.6000.16705" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY>
<DIV><FONT face=Arial size=2>Thanks Ulrich,</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>I just want to show the logic in its =
simplest form.
I am not a C++ guru indeed. I updated the code as long as I understand =
what you
mean. </FONT><FONT face=Arial size=2>Before I put the updated code, =
I want to
ask you a couple of questions about your comments:</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>You said : "</FONT><FONT face=Arial
size=2>...Further, your class is still default-constructible, copyable =
and
assignable."</FONT></DIV>
<DIV><FONT face=Arial size=2>Do you mean that I should =
implement a copy
constructor to handle assignment and copy?</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>You said : "InterlockedExchange() takes =
a pointer
to a volatile LONG. While this is automatically added in a function =
call,
it is still necessary in isInOrder()..."</FONT></DIV>
<DIV><FONT face=Arial size=2>All assignments to m_lRunningOrder =
are done by
Interlocked manner. So, I think no visibilty issue would be =
introduced even
though the variable is not volatile. Correct???</DIV></FONT>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial
size=2>////////////////////////////////////////////////////////////////=
/////////////</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>class
Sequencer<BR>{ <BR>public: <BR> <FONT
color=#ff0000>explicit</FONT> Sequencer (LONG lMaxSequence) : =
</FONT></DIV>
<DIV><FONT face=Arial size=2> =
m_lCurrentSequence (0),
</FONT></DIV>
<DIV><FONT face=Arial size=2> =
m_lRunningOrder (0),
</FONT></DIV>
<DIV><FONT face=Arial =
size=2> m_lMaxSequence
(lMaxSequence)<BR> {<BR> =
}<BR> </FONT></DIV>
<DIV><FONT face=Arial size=2> // Returns =
next available
sequence number. If the current sequence is equal to max sequence =
number
then zero returns.</FONT></DIV>
<DIV><FONT face=Arial size=2> // Should =
be called
before start an operation which need to be in-order</FONT></DIV>
<DIV><FONT face=Arial size=2> LONG =
getNextSequence
()<BR> {<BR>
LONG lCurrentSequence,
lNextSequence;<BR> =
while
(true)<BR>
{<BR> =
InterlockedExchange (&lCurrentSequence, m_lCurrentSequence); =
// Make
local copy of the
variable.<BR> =
lNextSequence = (lCurrentSequence == m_lMaxSequence ? 0 : =
lCurrentSequence + 1);
// Calculate next sequence number. If current sequence is equal to =
max then
next sequence is
zero. <BR> &nbs=
p;
</FONT></DIV>
<DIV><FONT face=Arial
size=2> &nbs=
p; // If another
thread already changed the current sequence number then =
recalculate.
Otherwise update the sequence number and return next =
sequence.</FONT></DIV>
<DIV><FONT face=Arial
size=2> &nbs=
p; if
(lCurrentSequence == InterlockedCompareExchange =
(&m_lCurrentSequence,
lNextSequence, lCurrentSequence)) </FONT></DIV>
<DIV><FONT face=Arial
size=2> &nbs=
p;
{<BR>
break;<BR>
=
}<BR> <BR>
}<BR> =
return
lNextSequence; <BR> }</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2> // When =
an operation
is completed, this method should be called.</FONT></DIV>
<DIV><FONT face=Arial size=2> bool
updateRunningOrder (const LONG lSequence)<BR>
{<BR> if (isInOrder
(lSequence)) // Allow only in-order
operations.<BR>
{</FONT></DIV>
<DIV><FONT face=Arial
size=2> &nbs=
p; //
If properly used then the class guarantees that only one thread can =
be here
at a time. So we can manuplate m_lRunnigOrder in thread-safe
manner.</FONT></DIV>
<DIV><FONT face=Arial
size=2><BR> =
LONG
lNewRunningOrder = (lSequence + 1) > m_lMaxSequence ? 0 : =
(lSequence +
1); // Next operation to complete. Again we circulate if =
we go
beyond the
max.<BR>  =
;
InterlockedExchange (&m_lRunningOrder,
lNewRunningOrder);<BR> =
return true;<BR>
}<BR> =
return
false;<BR> }</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2> bool isInOrder =
(const LONG
lSequence) <FONT =
color=#ff0000>const</FONT><BR>
{<BR> return (lSequence =
==
m_lRunningOrder);<BR> }</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2> </FONT><FONT =
face=Arial
size=2></FONT></DIV>
<DIV><FONT face=Arial size=2>private:</FONT></DIV>
<DIV><FONT face=Arial size=2> <FONT =
color=#ff0000>Sequencer ()
{};</FONT><BR> LONG
m_lMaxSequence; &nbs=
p; //
Sequence number limit to circulate.<BR> LONG
m_lCurrentSequence; =
// Current
sequence value for starting =
operations.<BR> <FONT
color=#ff0000>volatile</FONT> LONG =
m_lRunningOrder; // Next
operation to be completed.</FONT></DIV>
<DIV><FONT face=Arial size=2>};</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>"Ulrich Eckhardt" <</FONT><A
href="mailto:eckhardt@satorlaser.com"><FONT face=Arial
size=2>eckhardt@satorlaser.com</FONT></A><FONT face=Arial =
size=2>> wrote in
message </FONT><A =
href="news:bbjso5-44v.ln1@satorlaser.homedns.org"><FONT
face=Arial =
size=2>news:bbjso5-44v.ln1@satorlaser.homedns.org</FONT></A><FONT
face=Arial size=2>...</FONT></DIV><FONT face=Arial size=2>> =
Krat
wrote:<BR>> <BR>>> Hi,<BR>>> <BR>>> Recently I =
needed a
sequencer for my IOCP based socket server and<BR>>> developed one. =
I try
to implement it in lock-free manner. Your comments<BR>>> will bee
appreciated.<BR>>> <BR>>> The class is very small and all it =
do is
to maintain two numbers in thread<BR>>> safe manner. Before =
every
WSARecv call I get next available sequence<BR>>> number from =
sequencer and
put that number into my PerIoContext object.<BR>>> When a recv =
completion
occured then I check the sequence number to decide<BR>>> if the =
completion
occured in order. So one of the two numbers<BR>>> =
(m_lCurrentSequence)
represents call sequence and the other<BR>>> (m_lRunningOrder) =
represents
completion sequence. Here is the class :<BR>>> <BR>>> class
Sequencer<BR>>> {<BR>>>
public:<BR>>> Sequencer (LONG =
lMaxSequence)
: m_lCurrentSequence (0),<BR>>>
m_lRunningOrder<BR>>> (0), m_lMaxSequence
(lMaxSequence)<BR>>>
{<BR>>> }<BR>> <BR>> =
Single-argument
constructor that is not declared 'explicit' allows implicit<BR>> =
conversions,
which are usually bad. Further, your class is still<BR>>
default-constructible, copyable and assignable.<BR>>
<BR>>> LONG getNextSequence
()<BR>>>
{<BR>>> =
LONG
lCurrentSequence,
lNextSequence;<BR>>>  =
;
while
(true)<BR>>> &=
nbsp;
{<BR>>> =
InterlockedExchange
(&lCurrentSequence,<BR>>> &n=
bsp;
m_lCurrentSequence); lNextSequence = (lCurrentSequence
==<BR>>> &=
nbsp;
m_lMaxSequence ? 0 :<BR>>> lCurrentSequence +
1);<BR>>> &nbs=
p;
if (lCurrentSequence == InterlockedCompareExchange<BR>>>
(&m_lCurrentSequence, lNextSequence,
lCurrentSequence))<BR>>> &=
nbsp;
{<BR>>> =
break;<BR>>> &=
nbsp;
}<BR>>>
}<BR>>> return
lNextSequence;<BR>>> }<BR>> <BR>> Inconsistent =
formatting,
making it harder to understand what's going on.<BR>> Further, the =
whole code
is undocumented. Documenting the design of code<BR>> often leads to =
the
discovery of logic errors and allows maintenance by<BR>> =
others.<BR>>
<BR>>> bool isInOrder (const LONG =
lSequence)<BR>>>
{<BR>>> return (lSequence =
==
m_lRunningOrder);<BR>>> }<BR>> <BR>> Should be =
const.<BR>>
<BR>>> bool updateRunningOrder (const LONG
lSequence)<BR>>> =
{<BR>>>
if (isInOrder =
(lSequence))<BR>>>
{<BR>>> =
// Safe
region...<BR>>> &nbs=
p;
LONG lNewRunningOrder = (lSequence + 1) > m_lMaxSequence ? 0 =
:<BR>>>
(lSequence +
1);<BR>>> &nbs=
p;
InterlockedExchange (&m_lRunningOrder,
lNewRunningOrder);<BR>>> &=
nbsp;
return true;<BR>>>
}<BR>>> return
false;<BR>>> }<BR>>> <BR>>> =
private:<BR>>>
LONG m_lMaxSequence;<BR>>> LONG
m_lCurrentSequence;<BR>>> LONG m_lRunningOrder;<BR>>>
};<BR>> <BR>> InterlockedExchange() takes a pointer to a volatile =
LONG.
While this is<BR>> automatically added in a function call, it is =
still
necessary in<BR>> isInOrder(). Why? Simple reason: the compiler =
implements
read-accesses to a<BR>> volatile in a way similar to the =
Interlocked*()
functions. In fact, a<BR>> simple InterlockedRead() function is =
missing from
that API.<BR>> <BR>> Uli<BR>> <BR>> -- <BR>> C++ FAQ: =
</FONT><A
href="http://parashift.com/c++-faq-lite"><FONT face=Arial
size=2>http://parashift.com/c++-faq-lite</FONT></A><BR><FONT =
face=Arial
size=2>> <BR>> Sator Laser GmbH<BR>> =
Gesch=C3=A4ftsf=C3=BChrer: Thorsten F=C3=B6cking,
Amtsgericht Hamburg HR B62 932<BR>></FONT></BODY></HTML>
------=_NextPart_000_0016_01C90C39.8A108F20--