Monday, November 28, 2011

Atomic interface initialization

OmniThreadLibrary includes (in the OtlSync unit) a neat record called TOmniCS which wraps IOmniCriticalSection interface (which in itself is just a wrapper around the TCriticalSection) and allows you to use it without an explicit initialization. You just declare a variable of the TOmniCS type in your code and then call Acquire and Release methods of this variable and everything is handled for you.

type
  TOmniCS = record
  strict private
    ocsSync: IOmniCriticalSection;
    function  GetSyncObj: TSynchroObject;
  public
    procedure Initialize;
    procedure Acquire; inline;
    procedure Release; inline;
    property SyncObj: TSynchroObject read GetSyncObj;
  end;
As records don’t provide automatic initialization via parameterless constructor, the code is slightly tricky. The record contains a field (ocsSync) that contains the interface reference used to do real work. This interface is initialized in the Initialize method, which is in turn called from the Acquire and Release.

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

Destruction is automatically handled by the compiler when the record goes out of scope.

Keep in mind – although you cannot automatically initialize a record, the compiler will make sure that all reference-counted fields are correctly initialized to 0 when the record is allocated on the stack and that all such fields are correctly cleaned up when the record can no longer be accessed from the code (goes out of scope). Because of that you can freely use interfaces and strings inside records.
In the TOmniCS, however, the initialization becomes the tricky part. A critical section is by definition used from multiple threads (there’s no need for a critical section if you’re using only one thread) and consequently two threads can call Acquire at exactly the same time. This implies that Initialize must be implemented atomically – that is it must modify the ocsSync field in such a manner that only one of these Initialize calls will create new interface and the other will use the interface that was created by the first thread.
The atomicity can be achieved by using yet another critical section (but who would then initialize it?) or by using interlocked instructions (which are, in simple words, CPU instructions that are guaranteed to either execute fully or not at all, even when they occur at the same time on multiple processors).
TOmniCS uses the following code to initialize an interface:

procedure TOmniCS.Initialize;
var
  syncIntf: IOmniCriticalSection;
begin
  Assert(cardinal(@ocsSync) mod 4 = 0, 
    'TOmniCS.Initialize: ocsSync is not 4-aligned!');
  if not assigned(ocsSync) then begin
    syncIntf := CreateOmniCriticalSection;
    if InterlockedCompareExchange(
      PInteger(@ocsSync)^, integer(syncIntf), 0) = 0 
    then
      pointer(syncIntf) := nil;
  end;
end;
First it checks the alignment of the ocsSync field because all parameters to interlocked instructions must lie on correctly aligned memory addresses. Then it checks if the ocsSync field was already initialized. Nothing needs to be done if initialization has already occurred. Otherwise, the code optimistically creates a new critical section and stores it in a local variable. (Optimistically, because it assumes that the critical section will be later stored in the ocsSync field.)
Then the InterlockedCompareExchange is called. It takes three parameters – a destination address, an exchange data and a comparand. The functionality of the code can be represented by the following pseudocode:

function InterlockedCompareExchange(var destination: integer; 
  exchange, comparand: integer): integer;
begin
  Result := destination;
  if destination = comparand then
    destination := exchange;
end;
The trick here is that this code is all executed inside the CPU, atomically. The CPU ensures that the destination value is not modified (by another CPU) during the execution of the code.
It is hard to understand (interlocked functions always make my mind twirl in circles) but basically it reduces to two scenarios:
  1. Function returns 0 (old, uninitialized value of ocsSync), and ocsSync is set to new critical section (stored in syncIntf).
  2. Function returns a critical section (old, just initialized value of ocsSync) and ocsSync is not modified.
In yet another words – InterlockedCompareExchange either stores new interface in the ocsSync and returns 0 or does nothing and leaves already initialized ocsSync intact.
In the first scenario we now have two variables (ocsSync and syncIntf) initialized with the same interface value but the reference count of this interface is only 1 (Delphi doesn’t know that we copied the value behind the scenes) so we have to clear the temporary variable without decreasing the reference count by treating it as a pointer and assigning it a nil value.
There are few problems with this code:

  • It doesn’t check alignment of the syncIntf variable.
  • Alignment is always checked, not just when InterlockedCompareExchange is used.
  • It doesn’t work if the program is compiled to 64-bit code.
  • It is complicated.

Atomic initializer to the rescue!

When implementing background worker abstraction in the OmniThreadLibrary [to be released really really soon] I stumbled into a similar problem. A work item object contained a cancellation token interface but I only wanted this interface to be initialized on first use as most programs won’t use the cancellation token at all. Again, a work item can be accessed from multiple threads at once and I would have to use InterlockedCompareExchange to initialize it.
I started by copying the code from TOmniCS.Initialize but then I noticed that it will not work correctly in 64-bit code and that got me started thinking about how to write a generic atomic interface initializer. After all, I don’t want to fix multiple parts of code when I find a problem with the initializer (like the inability to work correctly in 64-bit code).
After some head-scratching I wrote the following class definition:

type
  Atomic<T: IInterface> = class
    type TInterfaceFactory = reference to function: T;
    class function Initialize(var storage: T; factory: TInterfaceFactory): T;
  end;
Generics and anonymous functions to the rescue! :)

class function Atomic<T>.Initialize(var storage: T; factory: TInterfaceFactory): T;
var
  tmpIntf: T;
begin
  if not assigned(storage) then begin
    Assert(cardinal(@storage) mod SizeOf(pointer) = 0, 
      'Atomic<T>.Initialize: storage is not properly aligned!');
    Assert(cardinal(@tmpIntf) mod SizeOf(pointer) = 0, 
      'Atomic<T>.Initialize: tmpIntf is not properly aligned!');
    tmpIntf := factory();
    if InterlockedCompareExchangePointer(
      PPointer(@storage)^, PPointer(@tmpIntf)^, nil) = nil 
    then
      PPointer(@tmpIntf)^ := nil;
  end;
  Result := storage;
end;
The code is built around the same pattern as TOmniCS.Initialize with few changes:

  • Alignment is checked against the pointer size, so it would work properly in 32-bit and 64-bit code.
  • Alignment is checked for both parameters of the interlocked function.
  • Alignment is checked only if interlocked function will be called.
  • InterlockedCompareExchangePointer is used instead of InterlockedCompareExchange as it works with the native pointer size data on 32-bit and 64-bit targets.
  • Typecasting is more complicated to work with the generics (but the meaning is the same).
  • A function that creates new interface (factory) is passed as parameter. It is declared as an anonymous function, which allows you to also use a method or a function as an initializer, courtesy of the Delphi compiler.
  • Interface is also returned as a function result.
This allowed me to write a very simple function that atomically creates IOmniCancellationToken the first time it is required.

function TOmniWorkItem.GetCancellationToken: IOmniCancellationToken;
begin
  Result := Atomic<IOmniCancellationToken>.Initialize(
    FCancellationToken, CreateOmniCancellationToken);
end;
It only needs two small supporting pieces of code – a field that stores the interface reference once it is created and a function that creates the interface-implementing object.

type  TOmniWorkItem = class(TInterfacedObject, IOmniWorkItem, IOmniWorkItemEx)
  strict private
    FCancellationToken: IOmniCancellationToken;
function CreateOmniCancellationToken: IOmniCancellationToken;
begin
  Result := TOmniCancellationToken.Create;
end;
And what about TOmniCS.Initialize? I fixed the code but as it has to work in Delphi 2007 I couldn’t use Atomic<T>.Initialize there :( C’est la vie.

7 comments:

  1. Great pattern, Primoz! That's what I was lacking in OTL (lazy initialization from multiple threads) :) Thanks a lot!
    You can also look at LazyInit from .NET4 which implements different scenarios of lazy initialization (for example, it can create an instance of an object as a singleton (your case) or single instance per each thread/task(?)).
    For more info, please look here:
    http://blogs.msdn.com/b/pedram/archive/2008/06/02/coordination-data-structures-lazyinit-t.aspx

    ReplyDelete
  2. I updated the code to also work with classes.

    Thanks for the link, I'll be checking it out.

    ReplyDelete
  3. I just opened this project from the SVN repository and when I tried to install OmniThreadLibraryDesignTimeXE2 I get a compile error [DCC Error] OtlSync.pas(579): E2506 Method of parameterized type declared in interface section must not use local symbol 'InterlockedCompareExchangePointer'

    Thanks for making what appears to be such a great project. I'm hoping to replace some of my naive timer-based code.

    ReplyDelete
  4. Sorry, I forgot to commit new OtlOptions.inc. This was fixed five minutes ago.

    ReplyDelete
  5. >>I updated the code to also work with classes.

    Thanks again!

    ReplyDelete
  6. I think, that it is also worth mentioning, that the object/interface, that we're initializing with optimistic initializer could be possibly created more than once (the thing that could not happen with pessimistic locking initializer), so possible redundant constructor calls (and immediate destructor calls) should not cause any side effects.

    ReplyDelete
  7. Very true. Pessimistic initializing is now available via Locked.Initialize.

    ReplyDelete