Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #2249

Her is my algorithm of the scalable LW_RWLockX

Cross-posted to 2 groups.

Show all headers | View raw

Hello,

I have not patented my algorithms, so i am posting them on Usenet
to be able to have a confirmation that those algorithms are my inventions.


So here is my scalable LW_RWLockX a starvation-free and scalable
RWLock.


{*************************************************************
*      Module: Scalable RWLOCK
*      Version: 3.06
*      Author: Amine Moulay Ramdane
*     Company: Cyber-NT Communications
*
*       Email: aminer@videotron.ca
*     Website: http://pages.videotron.com/aminer/
*        Date: September 12, 2013
*    Last update: March 23, 2014
*
* Copyright © 2013 Amine Moulay Ramdane.All rights reserved
*
*************************************************************}

unit LW_RWLOCKX;

{$I defines.inc}

{$ifdef FPC}
{$mode delphi}
{$endif}

{$IFDEF FPC}
{$ASMMODE intel}
{$ENDIF FPC}

interface

uses {$IF defined(Windows32) or  defined(Windows64) }
    Windows,
   {$IFEND}
sysutils,syncobjs,mtpcpu,TicketSpinlock,LW_EventCount,lw_alock;

const
   Alignment = 64; // alignment, needs to be power of 2

type

{$IFDEF CPU64}
int = int64;
Long = uint64;
{$ENDIF CPU64}
{$IFDEF CPU32}
int = integer;
Long = longword;
{$ENDIF CPU32}

typecache1  = array[0..14] of integer;
typecache2  = array[0..13] of integer;

MyRecord = Record
   FCount1:int;
   {$IFDEF CPU32}
   cache:typecache1;
   {$ENDIF CPU32}
   {$IFDEF CPU64}
   cache:typecache2;
   {$ENDIF CPU64}
end;

MyArray = array[0..0] of MyRecord;

MyRecord2 = Record
   FCount2:int;
   {$IFDEF CPU32}
   cache:typecache1;
   {$ENDIF CPU32}
   {$IFDEF CPU64}
   cache:typecache2;
   {$ENDIF CPU64}
end;

MyRecord3 = Record
   FCount3:int;
   {$IFDEF CPU32}
   cache:typecache1;
   {$ENDIF CPU32}
   {$IFDEF CPU64}
   cache:typecache2;
   {$ENDIF CPU64}
end;



MyRecord7 = Record
   nbr3:int;
   {$IFDEF CPU32}
   cache:typecache1;
   {$ENDIF CPU32}
   {$IFDEF CPU64}
   cache:typecache2;
   {$ENDIF CPU64}
end;

MyRecord4 = Record
   nbr:int;
   {$IFDEF CPU32}
   cache:typecache1;
   {$ENDIF CPU32}
   {$IFDEF CPU64}
   cache:typecache2;
   {$ENDIF CPU64}
end;


PMyRecord1 = ^MyArray;
PMyRecord2 = ^MyRecord2;
PMyRecord3 = ^MyRecord3;
PMyRecord4 = ^MyRecord4;


TRWLOCK = class
   private
Buffer1: pointer;
Buffer2: pointer;
Buffer3: pointer;
Buffer4: pointer;
FCount1: PMyRecord1;
FCount2: PMyRecord2;
FCount3: PMyRecord3;
nbr: PMyRecord4;

{$IF defined(Windows32) or  defined(Windows64) }
   FFileMapping1,FFileMapping2,FFileMapping3,FFileMapping4:THandle;
{$ELSE}

{$IFEND}
Fname:string;
mysleep:integer;
lock:TTicketSpinlock;
event1,event2:TLW_EventCount;
function GetUProcess: Boolean;
public
      constructor Create(const Name: string='';mssleep:integer=0);
     destructor  Destroy; override;

     procedure RLock(var myid:integer);
     procedure RUnlock(myid:integer);
     procedure WLock;
     procedure WUnlock;
   end; { TMREW }

implementation

{$IF defined(WIN32) or  defined(WIN64) }
function SwitchToThread: BOOL; stdcall; external kernel32 name 
'SwitchToThread';

//function GetCurrentProcessorNumber: longword; stdcall; external 
//kernel32 name 'GetCurrentProcessorNumber';

{$IFEND}


{$IF defined(CPU64) }
function LockedCompareExchange(CompareVal, NewVal: Int; var Target: 
int): Int; overload;
asm
mov rax, rcx
lock cmpxchg [r8], rdx
end;
{$IFEND}
{$IF defined(CPU32) }
function LockedCompareExchange(CompareVal, NewVal: int; var Target: 
int): int; overload;
asm
lock cmpxchg [ecx], edx
end;
{$IFEND}


function CAS(var Target:int;Comp ,Exch : int): boolean;
var ret:int;
begin

ret:=LockedCompareExchange(Comp,Exch,Target);
if ret=comp
  then result:=true
  else result:=false;

end; { CAS }


function LockedExchangeAdd(var Target: int; Value: int): int;
asm
         {$IFDEF CPU32}
         // --> EAX Target
         //     EDX Value
         // <-- EAX Result
         MOV     ECX, EAX
         MOV     EAX, EDX
         //     ECX Target
         //     EAX Value
         LOCK XADD [ECX], EAX
         {$ENDIF CPU32}
         {$IFDEF CPU64}
         // --> RCX Target
         //     RDX Value
         // <-- RAX Result
         MOV     RAX, RDX
         //     RCX Target
         //     RAX Value
         LOCK XADD [RCX], RAX
         {$ENDIF CPU64}
end;

function GetCurrentProcessorNumber:long;
asm
{$IFDEF CPU32}
    push ebx
    mov eax, 1
    CPUID
    shr ebx, 24
    mov eax, ebx
    pop ebx
{$ENDIF CPU32}
{$IFDEF CPU64}
    push rbx
     mov rax, 1
    cpuid
    shr rbx, 24
    mov rax, rbx
    pop rbx
   {$ENDIF CPU64}
end;

constructor TRWLOCK.Create(const Name: string='';mssleep:integer=0);

var i:integer;
begin

FName := Name;

if (mssleep < 0) or (mssleep > 1)
then
raise Exception.Create('Error from the constructor: milliseconds sleep 
must be 0 or 1..');

mysleep:=mssleep;


{$IF defined(threads)}
       Buffer1 := AllocMem((GetSystemThreadCount*SizeOf(MyRecord)) + 
Alignment); // 64 byte alignment.


        FCount1 := PMyRecord1((int(Buffer1) + Alignment -1) and not 
(Alignment -1));

     	
Buffer2 := AllocMem(SizeOf(MyRecord2) + Alignment);
FCount2 := PMyRecord2((int(Buffer2) + Alignment - 1)
                            and not (Alignment - 1));

Buffer3 := AllocMem(SizeOf(MyRecord3) + Alignment);
FCount3 := PMyRecord3((int(Buffer3) + Alignment - 1)
                            and not (Alignment - 1));

Buffer4 := AllocMem(SizeOf(MyRecord4) + Alignment);
nbr := PMyRecord4((int(Buffer4) + Alignment - 1)
                            and not (Alignment - 1));


lock:=TTIcketSpinlock.create('lock'+name);
event1:=TLW_EventCount.create('event1'+name);
event2:=TLW_EventCount.create('event2'+name);

{$ELSE}
if Name = '' then
   begin

     FFileMapping1 := 0;FFileMapping2 := 0;FFileMapping3 := 
0;FFileMapping4 := 0;

Buffer1 := AllocMem((GetSystemThreadCount*SizeOf(MyRecord)) + 
Alignment); // 64 byte alignment.

         FCount1 := PMyRecord1((int(Buffer1) + Alignment -1)
                            and not (Alignment -1));

Buffer2 := AllocMem(SizeOf(MyRecord2) + Alignment);
FCount2 := PMyRecord2((int(Buffer2) + Alignment - 1)
                            and not (Alignment - 1));

Buffer3 := AllocMem(SizeOf(MyRecord3) + Alignment);
FCount3 := PMyRecord3((int(Buffer3) + Alignment - 1)
                            and not (Alignment - 1));

Buffer4 := AllocMem(SizeOf(MyRecord4) + Alignment);
nbr := PMyRecord4((int(Buffer4) + Alignment - 1)
                            and not (Alignment - 1));

lock:=TTicketSpinlock.create('lock'+name);
event1:=TLW_EventCount.create('event1'+name);
event2:=TLW_EventCount.create('event2'+name);
   end
   else
   begin

     FFileMapping1 := Windows.CreateFileMapping(INVALID_HANDLE_VALUE, 
nil, PAGE_READWRITE,
       0, (GetSystemThreadCount*SizeOf(typecache1)) + Alignment, 
PChar('TRWLOCKX_MMF1_' + Name));
     Assert(FFileMapping1 <> 0);
     Buffer1 := Windows.MapViewOfFile(FFileMapping1, FILE_MAP_WRITE, 0, 
0, 0);
     Assert(Buffer1 <> nil);

FCount1 := PMyRecord1((int(Buffer1) + Alignment - 1)
                            and not (Alignment - 1));

FFileMapping2 := Windows.CreateFileMapping(INVALID_HANDLE_VALUE, nil, 
PAGE_READWRITE,
       0, SizeOf(MyRecord2)+ Alignment, PChar('TRWLOCKX_MMF2_' + Name));
    Assert(FFileMapping2 <> 0);
     Buffer2 := Windows.MapViewOfFile(FFileMapping2, FILE_MAP_WRITE, 0, 
0, 0);
     Assert(Buffer2 <> nil);

  FCount2 := PMyRecord2((int(Buffer2) + Alignment - 1)
                            and not (Alignment - 1));


FFileMapping3 := Windows.CreateFileMapping(INVALID_HANDLE_VALUE, nil, 
PAGE_READWRITE,
       0, SizeOf(MyRecord3)+ Alignment, PChar('TRWLOCKX_MMF3_' + Name));
    Assert(FFileMapping3 <> 0);
     Buffer3 := Windows.MapViewOfFile(FFileMapping3, FILE_MAP_WRITE, 0, 
0, 0);
     Assert(Buffer3 <> nil);

FCount3 := PMyRecord3((int(Buffer3) + Alignment - 1)
                            and not (Alignment - 1));


FFileMapping4 := Windows.CreateFileMapping(INVALID_HANDLE_VALUE, nil, 
PAGE_READWRITE,
       0, SizeOf(MyRecord4)+ Alignment, PChar('TRWLOCKX_MMF4_' + Name));
    Assert(FFileMapping4 <> 0);
     Buffer4 := Windows.MapViewOfFile(FFileMapping4, FILE_MAP_WRITE, 0, 
0, 0);
     Assert(Buffer4 <> nil);

nbr := PMyRecord4((int(Buffer4) + Alignment - 1)
                            and not (Alignment - 1));

lock:=TTicketSpinlock.create('lock'+name);
event1:=TLW_EventCount.create('event1'+name);
event2:=TLW_EventCount.create('event2'+name);

   end;
{$IFEND}


end;

destructor TRWLOCK.Destroy;
begin

{$IF defined(threads)}
FreeMem(Buffer1);
FreeMem(Buffer2);
FreeMem(Buffer3);
FreeMem(Buffer4);

{$ELSE}
if GetUProcess then
    begin
     FreeMem(Buffer1);
     FreeMem(Buffer2);
     FreeMem(Buffer3);
     FreeMem(Buffer4);

   end
   else
   begin
     Windows.UnmapViewOfFile(Buffer1);
     Windows.CloseHandle(FFileMapping1);
     Windows.UnmapViewOfFile(Buffer2);
     Windows.CloseHandle(FFileMapping2);
     Windows.UnmapViewOfFile(Buffer3);
     Windows.CloseHandle(FFileMapping3);
     Windows.UnmapViewOfFile(Buffer4);
     Windows.CloseHandle(FFileMapping4);
    end;

{$IFEND}
event1.free;
event2.free;
lock.free;

   inherited Destroy;

end;

function TRWLOCK.GetUProcess: Boolean;
begin
{$IF defined(threads)}
     result:=true;
{$ELSE}
   Result := ((FFileMapping1 = 0) and (FFileMapping2 = 0) and 
(FFileMapping3 = 0) and (FFileMapping4 = 0));

{$IFEND}

end;


//==============================================================================
procedure TRWLOCK.RLock(var myid:integer);


begin

myid:=GetCurrentProcessorNumber;

if (FCount3^.fcount3 = 1)
  then event1.wait;


LockedExchangeAdd(FCount1^[myid].fcount1,1);

if (FCount3^.fcount3 = 0)
then
else
  begin
   LockedExchangeAdd(nbr^.nbr,1);
   LockedExchangeAdd(FCount1^[myid].fcount1,-1);
   event2.wait;
   LockedExchangeAdd(FCount1^[myid].fcount1,1);;
   LockedExchangeAdd(nbr^.nbr,-1);

  end;

end;
//==============================================================================

procedure TRWLOCK.RUnlock(myid:integer);

begin

LockedExchangeAdd(FCount1^[myid].fcount1,-1);

end;
//==============================================================================

procedure TRWLOCK.WLock;

var i:integer;

begin

lock.enter;
repeat;
  event2.signal_all;
until nbr^.nbr=0;
event1.resetSignal;
//event2.resetSignal;
FCount3^.fcount3:=1;


for i:=0 to GetSystemThreadCount-1 do
  begin
    while (FCount1^[i].fcount1<>0)
     do
      begin
       //if mysleep=0 then sleep(0)
       //else sleep(1);
      end;
  end;

end;

//==============================================================================

procedure TRWLOCK.WUnlock;
var i:integer;
begin
FCount3^.fcount3:=0;
event1.setSignal;
event2.setSignal;
//sleep(0);
lock.leave;
end;
end.

===




Thank you,
Amine Moulay Ramdane.

Back to comp.programming.threads | Previous | Next | Find similar | Unroll thread

Thread

Her is my algorithm of the scalable LW_RWLockX aminer <aminer@toto.net> - 2014-04-24 18:33 -0700

csiph-web