ThreadSafe Lock Manager: [2] Code

After explaining the design, I’ll continue my trip into the depths of the lock manager by exploring the actual code. Let’s take a look at the public parts first.

[This code is implemented in the OtlSync unit, which is part of the OmniThreadLibrary distribution. You’ll have to fetch the OTL from the SVN to use it.]

The main interface to the lock manager is through the IOmniLockManager<K> interface or through the TOmniLockManager<K> class which implements that interface. Both are generic, as the type of the key (K) is not known in advance.

IOmniLockManager<K> implements three methods. Lock attempts to lock a key within a specified timeout and returns True if the lock was acquired. Unlock unlocks the same key. [Multiple nested Lock/Unlock calls are allowed in one thread – see the previous post for more details.] The last one, LockUnlock locks the key and returns an interface which will automatically unlock that key when it (the interface) is released. LockUnlock will return nil if the lock was not acquired.

type
    IOmniLockManagerAutoUnlock = interface
        procedure Unlock;
    end;

    IOmniLockManager<K> = interface
        function  Lock(const key: K; timeout_ms: cardinal): boolean;
        function  LockUnlock(const key: K; timeout_ms: cardinal):
      IOmniLockManagerAutoUnlock;
        function  Unlock(const key: K): boolean;
    end;

    TOmniLockManager<K> = class(TInterfacedObject, IOmniLockManager<K>)
    public
        class function CreateInterface(capacity: integer = 0): 
      IOmniLockManager<K>; overload;
        class function CreateInterface(comparer: IEqualityComparer<K>; 
      capacity: integer = 0): IOmniLockManager<K>; overload;
        constructor Create(capacity: integer = 0); overload;
        constructor Create(const comparer: IEqualityComparer<K>; 
      capacity: integer = 0); overload;
        destructor  Destroy; override;
        function  Lock(const key: K; timeout_ms: cardinal): boolean;
        function  LockUnlock(const key: K; timeout_ms: cardinal):
      IOmniLockManagerAutoUnlock;
        function  Unlock(const key: K): boolean;
    end;

The TOmniLockManager<K> implements these three functions while adding few constructors and a destructor.

There are two overloaded constructors, one accepting an optional capacity (initial estimate for the number of simultaneously locked keys; in reality that number can exceed the capacity without any problems) and another accepting both an equality comparer and a capacity. An equality comparer is an interface that provides comparison and hashing functionality for the key type K. If you will be locking only simple types (K being a string, an integer etc) you don’t have to provide a comparer as the code will use the default comparer for that type (details below).

There are also two class functions CreateInterface which function as a factory functions to create interface instances. [For example, you can use TOmniLockManager<string>.CreateInterface to create an instance of type IOmniLockManager<string>.]

Internal Data

The next code fragment contains private parts of the TOmniLockManager<K>.

  strict private type
        TNotifyPair = class(TGpDoublyLinkedListObject)
            Key   : K;
            Notify: TDSiEventHandle;
            constructor Create(const aKey: K; aNotify: TDSiEventHandle);
        end;
        TLockValue = record
            LockCount: integer;
            ThreadID : cardinal;
            constructor Create(aThreadID: cardinal; aLockCount: integer);
        end;
    strict private
        FComparer  : IEqualityComparer<K>;
        FLock      : TOmniCS;
        FLockList  : TDictionary<K,TLockValue>;
        FNotifyList: TGpDoublyLinkedList;
    strict private type
        TAutoUnlock = class(TInterfacedObject, IOmniLockManagerAutoUnlock)
        strict private
            FUnlockProc: TProc;
        public
            constructor Create(unlockProc: TProc);
            destructor  Destroy; override;
            procedure Unlock;
        end;

All currently locked keys are stored in the dictionary FLockList which is indexed by the key value and contains a (LockCount, ThreadID) pair for each key. The ThreadID field stores the ID of the thread that holds the lock and the LockCount contains the number of nested Lock calls.

Notification objects are stored in a doubly-linked list. [Single-linked list would do, but I just had TGpDoublyLinkedList class lying around.] This list contains TNotifyPair objects.

The TAutoUnlock nested type implements the LockUnlock functionality.

Implementation

Constructors are fairly trivial. One interesting point is how the internal FComparer field is set if external comparer was not provided. [This is an approach used by the TDictionary itself.]

constructor TOmniLockManager<K>.Create(const comparer: IEqualityComparer<K>;
    capacity: integer);
begin
    inherited Create;
    FComparer := comparer;
    if not assigned(FComparer) then
        FComparer := TEqualityComparer<K>.Default;
    FLockList := TDictionary<K,integer>.Create(capacity, FComparer);
    FNotifyList := TGpDoublyLinkedList.Create;
end;

The main workhorse of the lock manager is the Lock function. The first part – the repeat..until loop – tries to lock the key within the timeout_ms milliseconds (timeouts of 0 and INFINITE are supported). The code first checks if the key is already present in the dictionary. If not, it is added (with this, the lock is acquired), and the code exits.

If the key is found in the dictionary, the code checks if it was locked by the current thread. If true, the LockCount is incremented and updated in the dictionary (with this, the lock is reacquired) and the code exits. Otherwise, the code sets up an event, adds it to the notification list and waits for either the event to become signaled or for the timeout. [Of course, if timeout occurs, the Lock fails and returns False.]

If the event is signaled within the timeout, the code starts from the beginning – by checking whether the key exists in the dictionary etc. The reason for this complication is that access to the data structures (dictionary, notification list) must be done within the protection of a critical section but we must release this critical section before waiting or other threads would be blocked during that time.

At the very end, the code removes the notification event from the notification list (if that event was created at all) and destroys it.

function TOmniLockManager<K>.Lock(const key: K; timeout_ms: cardinal): boolean;
var
    lockData  : TLockValue;
    lockThread: integer;
    notifyItem: TGpDoublyLinkedListObject;
    startWait : int64;
    waitEvent : TDSiEventHandle;
    wait_ms   : integer;
begin
    Result := false;
    waitEvent := 0;
    startWait := DSiTimeGetTime64;

    repeat
        FLock.Acquire;
        try
            if not FLockList.TryGetValue(key, lockData) then begin
                // Unlocked
                FLockList.Add(key, TLockValue.Create(GetCurrentThreadID, 1));
                Result := true;
                break; //repeat
            end
            else if lockData.ThreadID = GetCurrentThreadID then begin
                // Already locked by this thread, increase the lock count
                Inc(lockData.LockCount);
                FLockList.AddOrSetValue(key, lockData);
                Result := true;
                break; //repeat
            end
            else if waitEvent = 0 then begin
                waitEvent := CreateEvent(nil, false, false, nil);
                FNotifyList.InsertAtTail(TNotifyPair.Create(key, waitEvent));
            end;
        finally FLock.Release; end;
        wait_ms := integer(timeout_ms) - integer(DSiTimeGetTime64 - startWait);
    until ((timeout_ms <> INFINITE) and (wait_ms <= 0)) or
                (WaitForSingleObject(waitEvent, cardinal(wait_ms)) = WAIT_TIMEOUT);

    if waitEvent <> 0 then begin
        FLock.Acquire;
        try
            for notifyItem in FNotifyList do
                if TNotifyPair(notifyItem).Notify = waitEvent then begin
                    notifyItem.Free;
                    break; //for notifyItem
                end;
            DSiCloseHandleAndNull(waitEvent);
        finally FLock.Release; end;
    end;
end;

Unlocking

Unlocking the key is simpler. The code either decrements the LockCount or removes the key from the dictionary (by that the lock on the key is released) and signals the first thread that is waiting on the same key. Again, everything is done under the protection of a critical section.

function TOmniLockManager<K>.Unlock(const key: K): boolean;
var
    lockData  : TLockValue;
    notifyItem: TGpDoublyLinkedListObject;
begin
    FLock.Acquire;
    try
        if not FLockList.TryGetValue(key, lockData) then
            raise Exception.Create('TOmniLockManager<K>.Unlock: Key not locked');
        if lockData.ThreadID <> GetCurrentThreadID then
            raise Exception.Create(
        'TOmniLockManager<K>.Unlock: Key was not locked by the current thread');
        if lockData.LockCount > 1 then begin
            Dec(lockData.LockCount);
            FLockList.AddOrSetValue(key, lockData);
        end
        else begin
            FLockList.Remove(key);
            for notifyItem in FNotifyList do
                if FComparer.Equals(TNotifyPair(notifyItem).Key, key) then begin
                    SetEvent(TNotifyPair(notifyItem).Notify);
                    break; //for notifyItem
                end;
        end;
    finally FLock.Release; end;
end;

That would be all for today. Next time, I’ll show the demo/test code and discuss the lock manager performance.