Performance cost of locking

.lock-cost: The cost of locking in performance terms are:

• .lock-cost.overhead: the overhead of claiming and releasing locks;
• .lock-cost.pause: the pauses caused by one thread being blocked on another thread.
• .lock-cost.wait: the time wasted by one thread being blocked on another thread.

.anal.perf.signif: .lock-cost.pause is significant if there are MPS functions that take a long time. Using more locks, e.g. having a lock per pool as well as a lock per arena, is a way of decreasing the locking conflict between threads (.lock-cost.pause and .lock-cost.wait). However this could increase .lock-cost.overhead significantly.

.anal.perf.work: But all MPS functions imply a small work-load unless a collection is taking place. In the case of a collection, in practice and certainly in the near future, all threads will most likely be suspended while the collection work is going on. (The pages being scanned will need to be unprotected which implies the mutator will have to be stopped.) We also have to remember that unless we are running on genuine multiprocessor .lock-cost.wait is irrelevant.

.anal.perf.alloc: During typical use we expect that it is allocation that is the most frequent activity. Allocation buffers (design.mps.buffer) are designed to allow allocation in concurrent threads without needing a lock. So the most significant time a thread spends in the MPS will be on a buffer-fill or during a collection. The next most significant use is likely to be buffer create and deletion, as a separate buffer will be required for each thread.

.anal.perf.lock: So overall the performance cost of locking is, I estimate, most significantly the overhead of calling the locking functions. Hence it would be undesirable from a performance point of view to have more than one lock.

Recursive vs binary locks

.anal.reentrance: The simplest way to lock the code safely is to define which code runs inside or outside the lock. Calling from the outside to the inside implies a lock has to be claimed. Returning means the lock has to be released. Control flow from outside to outside and from inside to inside needs no locking action. To implement this a function defined on the external interface needs to claim the lock on entry and release it on exit. Our code currently uses some external functions with the lock already held. There are two ways to implement this:

1. .recursive: Each external function claims a recursive lock.
   • simple;
   • have to worry about locking depth;
   • extra locking overhead on internal calls of external functions;
2. .binary: Each external function claims a binary lock. Replace each internal call of an external function with a call to a newly defined internal one.
   • more code
   • slightly easier to reason about

.anal.strategy: It seems that the .recursive strategy is the easiest to implement first, but could be evolved into a .binary strategy. (That evolution has now happened. tony 1999-08-31).

Locking Functions

ArenaEnter() and ArenaLeave() are used to claim and release the arena lock. To implement this:

• There is a lock for every arena. The arena class init function allocates the lock as well as the arena itself.
• ArenaInit() calls LockInit() on the lock and initializes the pointer to it from the arena.
• ArenaDestroy() calls LockFinish() on it.
• ArenaEnter() claims the lock.
• ArenaLeave() releases the lock.

Shared and non-shared data

Non-shared data is data for which no other thread has a handle on it. shared-non-mutable data is data which is never changed after initialisation. It may be re-initialised, if re-initialisation does not change its value. atomically updatable data is data which is not locked, but may be shared because it is in a consistent state before and after an update.

A function is "safe" if it may safely execute without exclusive access to the data it manipulates.

A "safe" function may:

• call other safe functions;
• manipulate non-shared data;
• read shared-non-mutable data;
• claim the arena lock around code which may manipulate shared data in the arena.

Each function in the external MPS interface falls into one of the following categories:

• calls ArenaEnter() on entry and ArenaLeave() on exit;
• uses PoolArena() to identify the arena, before claiming the lock;
• uses BufferPool() and PoolArena() to identify the arena, before claiming the lock;
• is not defined as external but is listed for explicitness;
• only claims the lock in otherwise unsafe situations (buffer code?);
• may be called externally but only in a situation where the arena lock is already held;
• is the unique accessor of its data.

So PoolArena() and BufferPool() must be "safe". pool->arena is shared-non-mutable. buffer->pool is shared-non-mutable.

Validation

We have to be careful about validation. Any function that is called from a arena-safe function without the arena-lock held, must itself be safe, or manipulating non-shared data.

For example, calling PoolIsValid() before claiming the lock would be wrong if PoolIsValid() is unsafe. Defining it to be safe would involve locking it, which if done in all similar situations would be very expensive.

Possibly remove validation from accessor methods; replace with signature check and IsValid() calls in callers of accessor functions.

Annotations?: - safe - non-shared - shared-non-mutable

Safe functions

Arena

• ArenaCreate() -- no shared data; no lock; calls LockInit().
• ArenaDestroy() -- no shared data; no lock (should only finish arena after use); calls LockFinish().
• ArenaDescribe() -- lock.

Root (for the purposes of locking this module can be thought of as external)

• RootCreate() -- calls create
• RootCreateTable() -- calls create
• create -- lock
• RootDestroy() -- lock
• RootDescribe() -- lock

will be attached to arena, can lock now.

Pool

• PoolCreate() / PoolCreateV() -- lock (Create calls CreateV which locks).
• PoolDestroy() -- lock
• PoolAlloc() -- lock
• PoolFree() -- lock
• PoolArena() -- accesses shared-non-mutable data only
• PoolDescribe() -- lock

Format

• FormatCreate() -- lock
• FormatDestroy() -- lock

Buffer

• BufferCreate() -- lock
• BufferDestroy() -- lock
• BufferFill() -- lock
• BufferTrip() -- lock
• BufferPool() -- accesses shared-non-mutable data only
• BufferDescribe() -- lock
• BufferCommit() -- "unsafe": buffer may be used by single thread only. (but safe wrt arena)
• BufferReserve() -- "unsafe": also

PoolClass (only shared data is static and non-mutable)

• PoolClass()
• PoolClassAMC()
• PoolClassMV()
• PoolClassMFS()

Sig (as with PoolClass, relies on static data reinitialised to constant value)

Collect

• Collect() -- lock

Thread

• ThreadRegister() -- lock
• ThreadDeregister() -- lock