Mutual exclusivity lock functions
[Pre-emptive, soft real-time scheduler]

Locks are guaranteeing mutually exclusive access to some resource. More...

Data Structures
struct	BX_LOCK
	Lock object. More...
Defines
#define	BX_LOCK_INIT(policy, ceiling)
	Static initialiser for a lock.
Functions
int	BX_LockInit (BX_LOCK *lock, BX_POLICY policy, unsigned ceilprio)
	Initialises a mutual exclusivity lock.
int	BX_LockObtain (BX_LOCK *lock, unsigned timeout)
	Obtains a lock.
int	BX_LockRelease (BX_LOCK *lock)
	Releases a lock.

---

Detailed Description

Locks are guaranteeing mutually exclusive access to some resource.

If you want to use the resource, you first obtain the lock. If the lock is already owned by an other process, you will be suspended until the other process releases it. Once you own the lock, you know that no other process can get it until you release it.
A lock is also known as a mutex or a binary semaphore.

If more than one process waits for a lock, the question arises which one of the waiting processes gets it when the current owner releases the lock. The kernel supports two policies, one is FIFO, where the processes are served according to their request order. The other is by priority, in which case the highest priority waiting process will get the lock.

There is an interesting phenomenon, though, that warrants consideration. Let's assume that we have two processes, a low priority one that we'll call L and a high priority one, H. Let L take the lock. Then, if H wakes up, it will suspend L as H has higher priority. Now if H wants to access the resource protected by the lock, it tries to obtain the lock. Since it is already owned by L, H will be suspended, L resumes execution and when it finishes with the resource and releases the lock, it will immediately be given to H. Thus, H becomes ready, L gets suspended and H can chug away doing whatever it has to.
Let us introduce a third process, M, which has a priority between that of L and H. As before, L takes the lock, H wakes up, tries to obtain the lock, gets suspended. However, before L could finish with the resource, M wakes up and starts a lengthy operation that has nothing to do with the protected resources. Since M has higher priority than L, L will be suspended. Since L is suspended, it can not release the lock. Therefore H is also suspended as long as M is running, even though they do not compete for the resource. In effect, a high priority process is held up by a lower priority one. This phenomena is known as priority inversion. There are two methods commonly used to avoid it.

• Priority ceiling
  A lock has a priority associated with it, which is usually the priority of the highest priority process that can obtain the lock. If a process gets the lock, its priority is elevated to the level associated with the lock and dropped back to its normal level when the lock is released. This way it is guaranteed that as long as process holds the resource, no process at a lower priority that the highest priority potential lock owner can suspend it. While this method avoids priority inversion, it has two problems. One is that you need to know a priori the highest priority of the processes that can take the lock. The other is that since a low priority process will be elevated to the lock's priority as soon as it takes the lock, it will stop all other processes below that high priority even if there's no competition for the lock.

• Priority inheritance
  This method solves the problems associated with priority ceiling. When a process gets the lock, nothing changes. However, if an other process comes to obtain the lock, then if the new process' priority is higher than that of the lock owner, then the owner's priority will be temporarily raised to that of the waiting process. If yet an other process comes to wait with an even higher priority, then the owner's priority will be raised again, to match that. In general, the lock owner's priority is raised to the largest of the priorities of the processes waiting for the lock.

While these methods seem simple enough, they get a bit complicated when you have multiple locks. Let us have two locks, A and B, using priority inheritance. If a process takes A and then goes to take B as well but B is already taken, then the process gets suspended on B. Naturally, B's owner's priority will be raised to match that of this process. Now if a third process with a priority even higher goes to wait on A, then the priority of the process that owns A is raised. That process waits on B, thus the priority of the owner of B must also be raised. So the kernel has to evaluate the ownership chain. The situation is even more complex when you have timeouts, because if a high priority process ceases to wait for a lock, you have to check if you can lower the priority of the lock owner.

Since the priority ceiling and inheritance mechanisms are orthogonal concepts to the ordering of the waiting queue, the locks support 6 different policies:

• Queue order is FIFO, no priority inheritance or ceiling
• Queue order is FIFO, priority ceiling
• Queue order is FIFO, priority inheritance
• Queue order is by priority, no priority inheritance or ceiling
• Queue order is by priority, priority ceiling
• Queue order is by priority, priority inheritance

Locks, like any other kernel object, are allocated by you in your memory. Before you can use a lock, you must initialise it, using either the BX_LOCK_INIT() static initialiser macro or the BX_LockInit() function.

---

Define Documentation

#define BX_LOCK_INIT	(	policy,
		ceiling		)

Value:

{                                                                   \
    .pmut = {                                                       \
        .wait = {                                                   \
            .type = BX_TYPE_LOCK,                                   \
            .head = NULL,                                           \
            .tail = NULL,                                           \
            .ftab = (struct _bx_poli *) (                           \
                    (policy) == BX_POLICY_PRIO ? &_bx_poli_prio :   \
                    (policy) == BX_POLICY_FPCL ? &_bx_poli_fpcl :   \
                    (policy) == BX_POLICY_FPIN ? &_bx_poli_fpin :   \
                    (policy) == BX_POLICY_PPCL ? &_bx_poli_ppcl :   \
                    (policy) == BX_POLICY_PPIN ? &_bx_poli_ppin :   \
                    &_bx_poli_fifo )                                \
        },                                                          \
        .ceil = (ceiling),                                          \
        .next = NULL,                                               \
        .prev = NULL,                                               \
        .proc = NULL,                                               \
        .prio = 0                                                   \
    }                                                               \
}

Static initialiser for a lock.

Parameters:

	policy	The locks waiting policy, one of BX_POLICY_FIFO, BX_POLICY_PRIO, BX_POLICY_FPCL, BX_POLICY_FPIN, BX_POLICY_PPCL, BX_POLICY_PPIN as defined by BX_POLICY .
	ceiling	The ceiling priority if the policy is BX_POLICY_FPCL or BX_POLICY_PPCL. In any other case its value is ignored.

---

Function Documentation

int BX_LockInit	(	BX_LOCK *	lock,
		BX_POLICY	policy,
		unsigned	ceilprio
	)

Initialises a mutual exclusivity lock.

Parameters:

	lock	Pointer to the lock to initialise
	policy	The process queueing policy of the lock. It must be one of BX_POLICY_FIFO, BX_POLICY_PRIO, BX_POLICY_PPCL, BX_POLICY_PPIN, BX_POLICY_FPCL or BX_POLICY_FPIN.
	ceilprio	The priority of the lock if it implements priority ceiling. For all other policies this argument is ignored.

Return values:

	>0	Success
	BX_ERR_PARAM	A lock doesn't support the given policy

Note:

If the lock uses priority ceiling or priority inheritance policy, quite a lot of code (and runtime) is needed to maintain the priorities through inheritance chains. Of course, if you do not use such policies, the relevant routines will not be called thus the runtime penalty associated with dynamic priorities will not hit you. The code size is a different issue. The kernel is a library, therefore only what is used will be linked into your code. If you statically initialise all your locks, and none of the uses the above mentioned policies, then the dynamic policy code will not be linked into your application. If, however, you call LockInit(), it can not know at compile time if you will pass it a policy that requires that code or not, therefore it will be linked into your code, even if you will never use it. It is a few KBs, so if you are a bit low on code space, you might be better off using static inits than calling LockInit().

Attention:

This function does not suspend the caller. This function should not be called from an ISR or delayed ISR. Note, however, that the function does not check this criteria, to allow initialisation of locks before the kernel is started (which must happen in IRQ context). In addition, during the initialisation interrupts are not disabled, therefore you must make sure that nothing will touch the lock while this function is running.

int BX_LockObtain	(	BX_LOCK *	lock,
		unsigned	timeout
	)

Obtains a lock.

This function obtains a lock. If the lock is available, then the caller will own the lock. If the lock is not available, then the caller will be suspended and placed on the waiting queue of the lock.

Parameters:

	lock	Pointer to the lock to get
	timeout	Timeout value. If it is 0xffffffff, that is, -1 cast to unsigned, then there is not time limit in waiting for the lock. If it is any other value, then it is the timeout in microseconds. If the caller can not get the lock within that time, then the call will return and indicate timeout. If the timeout is 0, then the caller will not be suspended and the function returns immediately if the lock is not available.

Return values:

	>0	The lock was obtained by the caller
	0	Timeout, the lock was not taken
	BX_ERR_ISOWNER	The lock was already owned by the caller
	BX_ERR_CONTEXT	The function was called from an ISR context
	BX_ERR_OBJECT	The passed object is not a lock or it was not initialised.
	BX_ERR_SUSPEND	The caller should be suspended but can not because its protection levels is higher than BX_PROT_COOP.

Note:

Although the timeout value is specified in microseconds, the actual resolution depends on the frequency of calls to the BX_TimerTick() function.

Attention:

This function should not be called from an ISR or delayed ISR. This function can suspend the caller.

int BX_LockRelease

(

BX_LOCK *

lock

)

Releases a lock.

The function can not be called from kernel or interrupt context. The caller must own the lock.

Parameters:

lock

Pointer to the lock to be released

Return values:

	>0	Success.
	BX_ERR_OBJECT	The pointer does not point to a lock object.
	BX_ERR_CONTEXT	The caller is not a user thread
	BX_ERR_NOTOWNER	The calling process does not own the lock

Attention:

This function can only be called from user context. This function does not suspend the caller but can cause a context switch if a higher priority process is woken up by the call.