[fpc-devel] LockFree Queue algorithm

[Martin Friebe]

You will need to test it, but the following may also work

procedure tFlQueue.push(const tm : tNodeQueue);
var
  newTemp,
  lastTail,
  newTail : integer;
begin
  newTemp := temp;
  while newTemp >= fsize begin
    // if it is true, every thread is going to attempt to fix it, before 
doing the increment.
    // this means no thread will increase the value
    //  => one thread will to succeed (since the only reason "temp NE 
newTemp" is that temp has been decreased)
    // newTemp is bigger than fsize, so the result can not become negative.
     
interlockedCompareExchange(pointer(temp),pointer(newTemp-fsize),pointer(newTemp));
     newTemp := temp;
  end;
  newTemp:=interlockedIncrement(temp) mod fsize; // make sure we are 
always in range
  lastTail:=newTemp-1;
  if lastTail < 0 then lastTail := fsize -1;
  setObject(lastTail,tm); // you can remove the "mod" in setobject
  repeat
    
pointer(newTail):=interlockedCompareExchange(pointer(tail),pointer(newTemp),pointer(lastTail));
  until (newTail=lastTail);
end;


The "repeat" at the end does still work. In order to set "tail" to "0" 
(newTemp=0) => "tail" must first get "9" (as lastTail will be 9).

Only flaw is, if fsize is close enough to the upper data tpye boundary, 
and enough threads do InterLockedInvrement, (after all having 
simultaneously passed the repeat at the start), then you can still run 
over the boundary.
However this can only happen if you have more threads, than 
(upperBoundary - fsize).
So you can specify, that it is save up to this amount of parallel threads



IMHO the unit should have a warning (in the comments) that there it is 
the users responsibility *not* to store more elements than fsize. There 
is no check, and you will loose data, if you try to do so.


But as I said, no warranty that this will work, I haven't done any 
testing...

Martin


DarekM wrote:
> Martin Friebe pisze:
>> What about a long running (eg daemon) application?
>>
>> If temp/tail hits the upper boundary of Integer?
>>
>> (If I understand it correctly)
>> I don't know if interlockedIncrement gives a boundary error, but if not,
>> it still fails.
>> - With currently integer, it gets a negative value, once crossing
>> 0x7fffffff, and SetObject will attempt to read/write out-of-bounds 
>> memory.
>> - Assuming temp/tail being unsigned: it will go from 0xffffffff to 0.
>> "0xffffffff mod fsize" may return a value greater 0, "0x00 mod fsize"
>> will be zero. You make an unexpected jump within the list.
>>
>
>
> Thats right.
> But I can avoid this.
> 1. make length of tab equal power of two
> 2. use longword instead of integer
> 3.instead MOD use   result:=tab[lp and  fmask];
> and fmask:=$F or $FF or $FFF
>
>
> Thanks to find bug.
>
>
> Darek
>
>
>
>
> _______________________________________________
> fpc-devel maillist  -  fpc-devel at lists.freepascal.org
> http://lists.freepascal.org/mailman/listinfo/fpc-devel