Tuesday, February 03, 2009

Hassle-free critical section

While writing multithreaded code I sometimes need a fine-grained critical section that will synchronize access to some small (very small) piece of code. In the OmniThreadLibrary, for example, there’s a class TOmniTaskExecutor which has some of its internals (for example a set of Option flags) exposed to both the task controller and the task itself (and those two by definition live in two different threads). Access to those internal fields is serialized with a critical section.

Usually, I need two or more such critical sections. And because I’m lazy and I don’t want to write creation/destruction code every time I need a fine-grained lock, I usually create only one critical section and use if for all such accesses. In other words, when thread 1 is accessing field 1 (protected with that one critical section), thread 2 will be blocked from accessing field 2 (because it is protected with the same critical section). I can live with that, because the frequency of such accesses is very low (or I would not be reusing the same critical section).

Still, I was not happy with this status quo but I didn’t know what to do (except creating more critical sections, of course). Then, while developing the new OTL thread pool, I got a great idea – records! Records need no explicit .Create. Let’s make this new critical section a record!

Let’s start with the use scenario. I want to be able to declare the critical section object …

  TOmniTaskExecutor = class
strict private
oteInternalLock: TOmniCS;
//...
end;

… and then use it without any initialization.

  oteInternalLock.Acquire;
try
if not assigned(oteCommList) then
oteCommList := TInterfaceList.Create;
oteCommList.Add(comm);
SetEvent(oteCommRebuildHandles);
finally oteInternalLock.Release; end;

There are only two problems to be solved. I had to make sure that critical section is created when the record is first used and destroyed when the owning object is destroyed. It turned out that this is quite a big only

Destruction

Let’s start with the simpler problem – destruction. The solution to automatic record cleanup is well-documented (at least if you follow Delphi blogs where they talk about such things …). In general, Delphi compiler doesn’t guarantee what the initial state of record fields will be, but there are two exceptions to this rule – all strings are initialized to an empty string and all interfaces to nil (which in both cases means that the fields holding strings/interfaces are initialized to 0). In addition to that, the compiler will free memory allocated for string fields and destroy interfaces (well, decrease the reference count) when record goes out of scope. If the record is declared inside a method, this will happen when the method exits and if it is declared as a class field, the cleanup will occur when the class is destroyed. In any case, you can be sure that the compiler will take care for strings and interfaces.

So we already know something – TOmniCS record will contain an interface field and an instance of the object implementing this interface will do the actual critical section allocation and access.

  IOmniCriticalSection = interface ['{AA92906B-B92E-4C54-922C-7B87C23DABA9}']
procedure Acquire;
procedure Release;
function GetSyncObj: TSynchroObject;
end; { IOmniCriticalSection }

TOmniCS = record
private
ocsSync: IOmniCriticalSection;
function GetSyncObj: TSynchroObject;
public
procedure Initialize;
procedure Acquire; inline;
procedure Release; inline;
property SyncObj: TSynchroObject read GetSyncObj;
end; { TOmniCS }

The implementation of the IOmniCriticalSection interface is trivial.

  TOmniCriticalSection = class(TInterfacedObject, IOmniCriticalSection)
strict private
ocsCritSect: TSynchroObject;
public
constructor Create;
destructor Destroy; override;
procedure Acquire; inline;
function GetSyncObj: TSynchroObject;
procedure Release; inline;
end; { TOmniCriticalSection }

constructor TOmniCriticalSection.Create;
begin
ocsCritSect := TCriticalSection.Create;
end; { TOmniCriticalSection.Create }

destructor TOmniCriticalSection.Destroy;
begin
FreeAndNil(ocsCritSect);
end; { TOmniCriticalSection.Destroy }

procedure TOmniCriticalSection.Acquire;
begin
ocsCritSect.Acquire;
end; { TOmniCriticalSection.Acquire }

function TOmniCriticalSection.GetSyncObj: TSynchroObject;
begin
Result := ocsCritSect;
end; { TOmniCriticalSection.GetSyncObj }

procedure TOmniCriticalSection.Release;
begin
ocsCritSect.Release;
end; { TOmniCriticalSection.Release }
function CreateOmniCriticalSection: IOmniCriticalSection;
begin
Result := TOmniCriticalSection.Create;
end; { CreateOmniCriticalSection }

Creation

The destruction part was trivial (once you know the trick, of course), but the creation is not. Delphi only guarantees that the ocsSync interface will be initialized to nil (or 0, if you prefer), nothing more than that.

The TOmniCS record offloads all hard work to the Initialize method. It is called from Acquire and GetSyncObj (a method that returns underlying critical section), but not from Release and that’s for a reason. If you call Release before first calling Acquire, it is clearly a programming error and program should crash – and it will because the ocsSync will be nil.

procedure TOmniCS.Acquire;
begin
Initialize;
ocsSync.Acquire;
end; { TOmniCS.Acquire }

function TOmniCS.GetSyncObj: TSynchroObject;
begin
Initialize;
Result := ocsSync.GetSyncObj;
end; { TOmniCS.GetSyncObj }

procedure TOmniCS.Release;
begin
ocsSync.Release;
end; { TOmniCS.Release }

Let’s finally solve the hard work. Before the critical section can be used, ocsSync interface must be initialized. In a single-threaded world we would just create a TOmniCriticalSection object and store it in the ocsSync field. In the multi-threaded world this is not possible.

Let’s think about what can happen if two Acquire calls are made at the same time from two threads. Thread 1 checks if ocsSync is initialized, finds that it’s not and loses its CPU slice. Thread 2 checks if ocsSync is initialized, finds that it’s not, initializes it, calls Acquire and loses its CPU slice. Thread 1 creates another TOmniCriticalSection object, stores it in the ocsSync field (overwriting the previous value, which will get its reference count decremented, which will destroy the implementing object) and calls Acquire. Because this Acquire will be using a critical section different from the Acquire in thread 2, it will succeed and both threads will have access to the protected data. Bad!

The trick is to store TOmniCriticalSecion in the ocsSync field with an atomic operation that will succeed if and only if the ocsSync is empty (nil, zero). And that’s a job for the InterlockedCompareExchange (ICE in short).

ICE takes three parameters – first is an address of the memory area we are trying to modify. Second is the new value and third is the expected value stored in the memory area we are trying to modify. The function returns the current value of the affected memory area. If this memory is not equal to the third parameter than ICE will do nothing.

Quite a mouthful, I know. That’s how it is used in practice:

procedure TOmniCS.Initialize;
var
syncIntf: IOmniCriticalSection;
begin
Assert(cardinal(@ocsSync) mod 4 = 0, 'TOmniCS.Initialize: ocsSync is not 4-aligned!');
while not assigned(ocsSync) do begin
syncIntf := CreateOmniCriticalSection;
if InterlockedCompareExchange(PInteger(@ocsSync)^, integer(syncIntf), 0) = 0 then begin
pointer(syncIntf) := nil;
Exit;
end;
DSiYield;
end;
end; { TOmniCS.Initialize }

Initialize checks if ocsSync is allocated. If not, it will create a new instance of the IOmniCriticalSection interface and store it in the local variable. Then it tries to store it in the ocsSync field with a call to the ICE. The third parameter tells the ICE that we expect ocsSync to contain all zeroes. If this is so, interface will be stored in the ocsSync and ICE will return 0 (otherwise, it will return current value of the ocsSync field). If ICE succeeded, we have to clear the local variable without decrementing interface reference count and we can exit. If ICE failed, we’ll give the other thread a time slice (after all, the other thread just created the critical section, therefore we can assume it will Acquire it, therefore the current thread would not be able to Acquire it and it can sleep a little) and retry.

And that’s how you get a hassle-free critical section. Ugly, I know, but it works.

Just a word of warning – don’t try to pass a TOmniCS record around. Eventually you’ll do an assignment somewhere (newCS := oldCS) and that would screw things out. Just pass the critical section (TOmniCS.SyncObj) and all will be fine.


5 comments:

  1. Hi - nice concept! I'm 'borrowing' the idea already ;-)

    One word of advise: To make this code future-proof, you'd better start using SizeOf(Pointer) everywhere you have it hardcoded as '4' right now. Also, Don't use Cardinal, PInteger and Integer casts over values that are basically pointers. Use IntPtr (signed integer with same size as a pointer) and UIntPtr (unsigned integer with same size as a pointer) instead.

    Delphi doesn't know about them yet (at least, the win32 version of Delphi), so I declare them as follows :

    type
    QWord = Int64; // This is necessary because Delphi doesn't support QWord (unsigned 64bit type).
    LongLong = QWord;

    Int32 = LongInt; // Signed 32 bits
    // Int64; // Signed 64 bits - already exists
    UInt32 = LongWord; // Unsigned 32 bits
    UInt64 = LongLong; // Unsigned 64 bits

    {$IFDEF CPU32}
    IntPtr = Int32;
    UIntPtr = UInt32;
    {$ELSE}
    {$IFDEF CPU64}
    IntPtr = Int64;
    UIntPtr = UInt64;
    {$ELSE}
    Target CPU unknown! Please correct this, so IntPtr and UIntPtr can be defined correctly!
    {$ENDIF}

    PIntPtr = ^IntPtr;
    PUIntPtr = ^UIntPtr;

    initialization
    Assert(SizeOf(IntPtr) = SizeOf(Pointer));
    Assert(SizeOf(UIntPtr) = SizeOf(Pointer));

    ReplyDelete
  2. I have no idea how Delphi64 will implement types so I'm just checking type compatibility in the initialization section:

    initialization
    Assert(SizeOf(TObject) = SizeOf(cardinal));
    Assert(SizeOf(pointer) = SizeOf(cardinal));

    When D64 is available, I'll fix things up ...

    ReplyDelete
  3. But I agree - using SizeOf(pointer) or checking that it is 4 is a must.

    ReplyDelete
  4. Anonymous11:55

    I agree that this concept is useful, but I have one question to implementation of TOmniCS.Initialize. I don't understand why to use a loop. I think it's possible to change "while" to "if" because second check of while condition always returns false.

    ReplyDelete
  5. I do agree, "if" should be equally effective here. "While" is a leftover from the previous implementation (which was not working).

    ReplyDelete