/* semMLib.c - mutual-exclusion semaphore library *//* Copyright 1984-2002 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history--------------------02k,03may02,pcm  removed possible NULL dereference in semMCreate () (SPR 76721)02j,19nov01,bwa  Corrected doc for semMCreate return value (SPR #71921).02i,09nov01,dee  add CPU_FAMILY != COLDFIRE in portable test02h,30oct01,bwa  Fixed semMGive() behaviour.02g,07sep01,bwa  Added VxWorks events support.02f,04sep98,cdp  make ARM CPUs with ARM_THUMB==TRUE use portable routines.02f,03mar00,zl   merged SH support into T202f,18dec00,pes  Correct compiler warnings02e,17feb98,cdp  undo 02d: put ARM back in list of optimised CPUs.02d,21oct97,kkk  undo 02c, take out ARM from list of optimized CPUs.02c,20may97,jpd  added ARM to list of optimised CPUs.02b,15oct96,dgp  doc: add caveats on priority inversion per SPR #688402a,24jun96,sbs  made windview instrumentation conditionally compiled01z,22oct95,jdi  doc: added bit values for semMCreate() options (SPR 4276).01y,19mar95,dvs  removed tron references.01x,03feb95,rhp  doc: propagate warning about semaphore deletion from semLib01w,09jun93,hdn  added a support for I80X8601z,14apr94,smb  fixed class dereferencing for instrumentation macros01y,15mar94,smb  modified instrumentation macros01x,24jan94,smb  added instrumentation macros01w,10dec93,smb  added instrumentation01v,23jan93,jdi  documentation cleanup for 5.1.01u,13nov92,jcf  semMCreate call semMLibInit for robustness.01t,02oct92,jcf  made semMGiveForce() work if called by owner.01s,28jul92,jcf  semM{Create,Init} call semMLibInit for robustness.01r,28jul92,jcf  changed semMTakeKern to semMPendQPut;semMTake uses semMPendQPut01q,18jul92,smb  Changed errno.h to errnoLib.h.01p,09jul92,rrr  changed xsignal.h to private/sigLibP.h01o,04jul92,jcf  added semMLibInit() to fill in semLib tables.01n,26may92,rrr  the tree shuffle01m,27apr92,rrr  added signal restarting01l,15sep91,ajm  added MIPS to list of optimized CPU's01k,04oct91,rrr  passed through the ansification filter                  -changed functions to ansi style		  -changed includes to have absolute path from h/		  -fixed #else and #endif		  -changed copyright notice01j,26sep91,hdn  added conditional flag for TRON optimized code.01i,05apr91,jdi	 documentation -- removed header parens and x-ref numbers;		 doc review by jcf.01h,24mar91,jdi  documentation cleanup.01g,16oct90,jcf  fixed priority inversion race in semMGive.01f,05oct90,dnw  made semMInit() be NOMANUAL.01e,30sep90,jcf  added semMGiveForce().01d,03aug90,jcf  documentation.01c,17jul90,dnw  changed to new objAlloc() call.01b,05jul90,jcf  optimized version now available.01a,20oct89,jcf  written based on v1b of semILib.*//*DESCRIPTIONThis library provides the interface to VxWorks mutual-exclusionsemaphores.  Mutual-exclusion semaphores offer convenient optionssuited for situations requiring mutually exclusive access to resources.Typical applications include sharing devices and protecting datastructures.  Mutual-exclusion semaphores are used by many higher-levelVxWorks facilities.The mutual-exclusion semaphore is a specialized version of the binarysemaphore, designed to address issues inherent in mutual exclusion, suchas recursive access to resources, priority inversion, and deletion safety.The fundamental behavior of the mutual-exclusion semaphore is identicalto the binary semaphore (see the manual entry for semBLib), except forthe following restrictions:    - It can only be used for mutual exclusion.    - It can only be given by the task that took it.    - It may not be taken or given from interrupt level.    - The semFlush() operation is illegal.These last two operations have no meaning in mutual-exclusion situations.RECURSIVE RESOURCE ACCESSA special feature of the mutual-exclusion semaphore is that it may betaken "recursively," i.e., it can be taken more than once by the task thatowns it before finally being released.  Recursion is useful for a set ofroutines that need mutually exclusive access to a resource, but may needto call each other.Recursion is possible because the system keeps track of which taskcurrently owns a mutual-exclusion semaphore.  Before being released, amutual-exclusion semaphore taken recursively must be given the same numberof times it has been taken; this is tracked by means of a count which isincremented with each semTake() and decremented with each semGive().The example below illustrates recursive use of a mutual-exclusion semaphore.Function A requires access to a resource which it acquires by taking `semM';function A may also need to call function B, which also requires `semM':.CS.ne 3    SEM_ID semM;    semM = semMCreate (...);.ne 8    funcA ()	{	semTake (semM, WAIT_FOREVER);	...	funcB ();	...	semGive (semM);	}.ne 6    funcB ()	{	semTake (semM, WAIT_FOREVER);	...	semGive (semM);	}.CEPRIORITY-INVERSION SAFETYIf the option SEM_INVERSION_SAFE is selected, the library adopts apriority-inheritance protocol to resolve potential occurrences of"priority inversion," a problem stemming from the use semaphores formutual exclusion.  Priority inversion arises when a higher-priority taskis forced to wait an indefinite period of time for the completion of alower-priority task.Consider the following scenario:  T1, T2, and T3 are tasks of high,medium, and low priority, respectively.  T3 has acquired some resource bytaking its associated semaphore.  When T1 preempts T3 and contends for theresource by taking the same semaphore, it becomes blocked.  If we could beassured that T1 would be blocked no longer than the time it normally takesT3 to finish with the resource, the situation would not be problematic.However, the low-priority task is vulnerable to preemption by medium-prioritytasks; a preempting task, T2, could inhibit T3 from relinquishing the resource.This condition could persist, blocking T1 for an indefinite period of time.The priority-inheritance protocol solves the problem of priority inversionby elevating the priority of T3 to the priority of T1 during the time T1 isblocked on T3.  This protects T3, and indirectly T1, from preemption by T2.Stated more generally, the priority-inheritance protocol assures thata task which owns a resource will execute at the priority of the highestpriority task blocked on that resource.  Once the task priority has beenelevated, it remains at the higher level until all mutual-exclusion semaphoresthat the task owns are released; then the task returns to its normal, or standard, priority.  Hence, the "inheriting" task is protected from preemption by any intermediate-priority tasks.The priority-inheritance protocol also takes into consideration a task'sownership of more than one mutual-exclusion semaphore at a time.  Such atask will execute at the priority of the highest priority task blocked onany of its owned resources.  The task will return to its normal priorityonly after relinquishing all of its mutual-exclusion semaphores that havethe inversion-safety option enabled.SEMAPHORE DELETIONThe semDelete() call terminates a semaphore and deallocates anyassociated memory.  The deletion of a semaphore unblocks tasks pendedon that semaphore; the routines which were pended return ERROR.  Takespecial care when deleting mutual-exclusion semaphores to avoiddeleting a semaphore out from under a task that already owns (hastaken) that semaphore.  Applications should adopt the protocol of onlydeleting semaphores that the deleting task owns.TASK-DELETION SAFETYIf the option SEM_DELETE_SAFE is selected, the task owning the semaphorewill be protected from deletion as long as it owns the semaphore.  Thissolves another problem endemic to mutual exclusion.  Deleting a taskexecuting in a critical region can be catastrophic.  The resource could beleft in a corrupted state and the semaphore guarding the resource would beunavailable, effectively shutting off all access to the resource.As discussed in taskLib, the primitives taskSafe() and taskUnsafe()offer one solution, but as this type of protection goes hand in hand withmutual exclusion, the mutual-exclusion semaphore provides the optionSEM_DELETE_SAFE, which enables an implicit taskSafe() with each semTake(),and a taskUnsafe() with each semGive().  This convenience is also moreefficient, as the resulting code requires fewer entrances to the kernel.CAVEATSThere is no mechanism to give back or reclaim semaphores automatically whentasks are suspended or deleted.  Such a mechanism, though desirable, is notcurrently feasible.  Without explicit knowledge of the state of the guardedresource or region, reckless automatic reclamation of a semaphore couldleave the resource in a partial state.  Thus if a task ceases executionunexpectedly, as with a bus error, currently owned semaphores will not begiven back, effectively leaving a resource permanently unavailable.  TheSEM_DELETE_SAFE option partially protects an application, to the extentthat unexpected deletions will be deferred until the resource is released.Because the priority of a task which has been elevated by the taking of amutual-exclusion semaphore remains at the higher priority until allmutexes held by that task are released, unbounded priority inversion situationscan result when nested mutexes are involved.  If nested mutexes are required,consider the following alternatives:.iP 1. 4Avoid overlapping critical regions..iP 2. Adjust priorities of tasks so that there are no tasks at intermediatepriority levels..iP 3. Adjust priorities of tasks so that priority inheritance protocol is notneeded..iP 4. Manually implement a static priority ceiling protocol using a non-inversion-save mutex.  This involves setting all blockers on a mutex to the ceiling priority, then taking the mutex.  After semGive, set the priorities back to the base priority. Note that this implementation reduces the queue to a fifo queue..LPINTERNAL:	WINDVIEW INSTRUMENTATIONLevel 1:	semMCreate() causes EVENT_SEMMCREATE	semMGiveForce() causes EVENT_SEMMGIVEFORCELevel 2:	N/ALevel 3:	N/AINCLUDE FILES: semLib.hSEE ALSO: semLib, semBLib, semCLib,.pG "Basic OS"*/#include "vxWorks.h"#include "errnoLib.h"#include "taskLib.h"#include "intLib.h"#include "eventLib.h"#include "private/eventLibP.h"#include "private/sigLibP.h"#include "private/objLibP.h"#include "private/semLibP.h"#include "private/windLibP.h"#include "private/workQLibP.h"#include "private/eventP.h"/* optimized version available for 680X0, MIPS, i86, SH, *//* COLDFIRE and ARM (excluding Thumb) */#if (defined(PORTABLE) || \     ((CPU_FAMILY != MC680X0) && \      (CPU_FAMILY != MIPS) && \      (CPU_FAMILY != I80X86) && \      (CPU_FAMILY != SH) && \      (CPU_FAMILY != COLDFIRE) && \      (CPU_FAMILY != ARM)) || \     ((CPU_FAMILY == ARM) && ARM_THUMB))#define semMLib_PORTABLE#endif/* globals */int semMGiveKernWork;			/* parameter space for semMGiveKern() *//* locals */LOCAL BOOL	semMLibInstalled;	/* protect from muliple inits *//********************************************************************************* semMLibInit - initialize the binary semaphore management package* * SEE ALSO: semLibInit(1).* NOMANUAL*/STATUS semMLibInit (void)    {    if (!semMLibInstalled)	{	semGiveTbl [SEM_TYPE_MUTEX]		= (FUNCPTR) semMGive;	semTakeTbl [SEM_TYPE_MUTEX]		= (FUNCPTR) semMTake;	if (semLibInit () == OK)	    semMLibInstalled = TRUE;	}    return ((semMLibInstalled) ? OK : ERROR);    }/********************************************************************************* semMCreate - create and initialize a mutual-exclusion semaphore** This routine allocates and initializes a mutual-exclusion semaphore.  The* semaphore state is initialized to full.** Semaphore options include the following:* .iP "SEM_Q_PRIORITY  (0x1)" 8* Queue pended tasks on the basis of their priority.* .iP "SEM_Q_FIFO  (0x0)"* Queue pended tasks on a first-in-first-out basis.* .iP "SEM_DELETE_SAFE  (0x4)"* Protect a task that owns the semaphore from unexpected deletion.  This* option enables an implicit taskSafe() for each semTake(), and an implicit* taskUnsafe() for each semGive().* .iP "SEM_INVERSION_SAFE  (0x8)"* Protect the system from priority inversion.  With this option, the task* owning the semaphore will execute at the highest priority of the tasks* pended on the semaphore, if it is higher than its current priority.  This* option must be accompanied by the SEM_Q_PRIORITY queuing mode.* .iP "SEM_EVENTSEND_ERR_NOTIFY (0x10)"* When the semaphore is given, if a task is registered for events and the* actual sending of events fails, a value of ERROR is returned and the errno* is set accordingly. This option is off by default.* .LP** RETURNS: The semaphore ID, or NULL if the semaphore cannot be created.** ERRNO* .iP "S_semLib_INVALID_OPTION"* Invalid option was passed to semMCreate.* .iP "S_memLib_NOT_ENOUGH_MEMORY"* Not enough memory available to create the semaphore.* .LP** SEE ALSO: semLib, semBLib, taskSafe(), taskUnsafe()*/SEM_ID semMCreate    (    int options                 /* mutex semaphore options */    )    {    SEM_ID semId;    if ((!semMLibInstalled) && (semMLibInit () != OK))	/* initialize package */        return (NULL);    if ((semId = (SEM_ID) objAlloc (semClassId)) == NULL)	return (NULL);    /* initialize allocated semaphore */    if (semMInit (semId, options) != OK)	{	objFree (semClassId, (char *) semId);	return (NULL);	}#ifdef WV_INSTRUMENTATION    /* windview - level 1 event logging */    EVT_OBJ_3 (OBJ, semId, semClassId,	       EVENT_SEMMCREATE, semId, options, semId->state);#endif    return (semId);    }/********************************************************************************* semMInit - initialize a mutual-exclusion semaphore** The initialization of a static mutual exclusion semaphore, or a mutual* exclusion semaphore embedded in some larger object need not deal* with allocation.  This routine may be called to initialize such a* semaphore.  The semaphore state is initialized to the full state.** Mutual exclusion semaphore options include the queuing style for blocked* tasks.  Tasks may be queued on the basis of their priority or* first-in-first-out.  These options are SEM_Q_PRIORITY and SEM_Q_FIFO* respectively.** The SEM_DELETE_SAFE option protects the task that currently owns the* semaphore from unexpected deletion.  This option enables an implicit* taskSafe() on each semTake(), and an implicit taskUnsafe() of every semGive().** The SEM_INVERSION_SAFE option protects the system from priority inversion.* This option must be accompanied by the SEM_Q_PRIORITY queuing mode.  With* this option selected, the task owning the semaphore will execute at the* highest priority of the tasks pended on the semaphore if it is higher than* its current priority.** RETURNS: OK, or ERROR if semaphore could not be initialized.** ERRNO: S_semLib_INVALID_OPTION** SEE ALSO: semLib, semBLib, semMCreate(), taskSafe(), taskUnsafe()** NOMANUAL*/STATUS semMInit    (    SEMAPHORE * pSemaphore,     /* pointer to mutex semaphore to initialize */    int         options         /* mutex semaphore options */    )    {    if ((!semMLibInstalled) && (semMLibInit () != OK))	/* initialize package */	return (ERROR);    if ((options & SEM_INVERSION_SAFE) && ((options & SEM_Q_MASK)==SEM_Q_FIFO))	{	errno = S_semLib_INVALID_OPTION;	return (ERROR);	}    if (semQInit (pSemaphore, options) != OK)	return (ERROR);    return (semMCoreInit (pSemaphore, options));    }/********************************************************************************* semMCoreInit - initialize a mutex semaphore with queue already initialized** To initialize a semaphore with some special queuing algorithm, this routine* is used.  This routine will initialize a mutual exclusion semaphore without* initializing the queue.** NOMANUAL*/STATUS semMCoreInit    (    SEMAPHORE   *pSemaphore,    /* pointer to mutex semaphore to initialize */    int         options         /* mutex semaphore options */    )    {    pSemaphore->semOwner = NULL;		/* no owner */    pSemaphore->recurse	 = 0;			/* init take recurse count */    pSemaphore->options	 = options;		/* initialize options */    pSemaphore->semType  = SEM_TYPE_MUTEX;	/* type is mutex */    eventInit (&pSemaphore->events);		/* initialize events */#ifdef WV_INSTRUMENTATION    /* windview - connect instrumented class for level 1 event logging */    if (wvObjIsEnabled)        objCoreInit (&pSemaphore->objCore, semInstClassId);    else        objCoreInit (&pSemaphore->objCore, semClassId);