/* windLib.c - internal VxWorks kernel library *//* Copyright 1984-2002 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history--------------------02a,22may02,jgn  updated tick counter to be 64 bit - SPR #7025501z,20mar02,bwa  windPendQRemove() now moves task out of the tick Q. (SPR                 #74673).01y,18dec00,pes  Correct compiler warnings01x,29oct97,cth  removed references to scrPad for WV2.001w,03dec96,dbt  Added intLock and intUnlock in windWdStart to protect the                 decrement of the defer start counter (fixed spr #7070).01v,24jun96,sbs  made windview instrumentation conditionally compiled01t,31jan95,tmk  added OBJ_VERIFY clause to windSemDelete()	   +rrr01s,27jan95,ms   windDestroy flushes the right saftey queue now	   +rrr01u,02feb94,smb  windPendQFlush no longer causes scratch-pad overflow SPR #298101t,24jan94,smb  added tid to EVENT_WINDTICKTIMEOUT01s,10dec93,smb  added instrumentation01r,13nov92,dnw  added include of smObjLib.h01q,19jul92,pme  Added windReadyQPut, made windDelete and windPendQRemove                 return STATUS, made windTickAnnounce set task return                 value acording to possible shared memory objects errors. 01p,04jul92,jcf  private headers.01n,05jun92,ajm  intCnt is now fixed, see excALib.s01o,26may92,rrr  the tree shuffle01n,15oct91,ajm  intCnt change for mips, this must be FIXED correctly soon01m,04oct91,rrr  passed through the ansification filter                  -changed functions to ansi style		  -changed includes to have absolute path from h/		  -changed VOID to void		  -changed copyright notice01l,28sep90,jcf  documentation.01k,04sep90,jcf  documentation.01j,03aug90,jcf  fixed bug in watchdog routine calling wdStart.01i,15jul90,jcf  fixed bug in watchdog handling which allowed work q to overflow01h,03jul90,jcf  added windPendQTerminate().		 added timer queue rollover algorithm.01g,26jun90,jcf  simplified priority inheritance algorithm.		 changed windSem*() to windPendQ*().01f,28aug89,jcf  modified to support version 2.0 of wind.01e,09aug89,gae  SPARCintized windDummyCreate.01d,19nov88,jcf  validated task id before operations undertaken.		   changed lstFirst, lstPrevious, lstNext to macros.01c,23aug88,gae  documentation.01b,12aug88,jcf	 cleanup.01a,12mar88,jcf	 written.*//*DESCRIPTIONThe VxWorks kernel provides tasking control services to an application.  Thelibraries kernelLib, taskLib, semLib, tickLib, and wdLib comprise the kernelfunctionality.  This library is internal to the VxWorks kernel and containsno user callable routines.INTERNALThis is a description of the architecture of Wind version 2.0.  The informationhere applies to the following libraries: kernelLib, taskLib, semLib, tickLib,wdLib, schedLib, workQLib, windLib, windALib, semALib, and workQALib.STATE MACHINEThe kernel is a small state machine.  Each task contains state information inthe status field.  The possible states in wind 2.0 are:    WIND_READY,				Ready for execution, in readyQHead.    WIND_DELAY,				Sleeping, in tickQHead.    WIND_PEND,				Blocked, in resource pendQHead.    WIND_PEND | WIND_DELAY,		Blocked w/timeout in pendQHead/tickQHead    WIND_SUSPEND,			Suspended, in no queue.    WIND_DELAY | WIND_SUSPEND,		Suspended sleeping, in tickQHead    WIND_PEND | WIND_SUSPEND,		Suspended blocked, in pendQHead.    WIND_PEND|WIND_DELAY|WIND_SUSPEND,  Susp blocked w/tout, pendQHead/tickQHead    WIND_DEAD				Extinct, gone, deceased, an Ex-Task.We provide a rich set of routines to move routines from state to another inthe aforementioned libraries.  The actual work of changing a task's state andshuffling it into the appropriate queue is done within this library as alower level call to the user routines elsewhere.  For instance taskSuspend()calls windSuspend().  This decomposition is not purely aesthetic, the separationis necessary as part of the mutual exclusion method used by the kernel.MUTUAL EXCLUSIONBy the time we arrive in the routines located here, higher level routines haveobtained mutual exclusion to all kernel queues by entering kernel state.  Theroutines located here have free reign over any kernel data structure.  Kernelstate is a powerful means of mutual exclusion, unfortunately preemption isdisabled for the duration of kernel state.  High preemptive latency underminesthe reactive latency of a real time system, so it is crucial to use thismechanism sparingly.  Indeed the basic design philosophy of the kernel is tokeep it as minimal as possible, while still capable of supporting higher levelfacilities.Kernel routines fit the template illuminated by taskResume():    if (kernelState)				/@ defer work if in kernel @/	{	workQAdd1 (windResume, tid);		/@ add work to kernel work q @/	return (OK);	}    kernelState = TRUE;				/@ KERNEL ENTER @/    windResume ((WIND_TCB *) tid);		/@ resume task @/    windExit ();				/@ KERNEL EXIT @/To enter kernel state one simply sets the global variable kernelState to TRUE.From that point, all kernel data structures are protected from contention.When finished with the kernel operation, kernel state is left via windExit()which sets kernelState back to FALSE.  Lets consider who, in fact, contendsfor the internal data structures.  An interrupt service routine is the onlypossible initiator of additional kernel work.  That is, once a system enterskernel state the only way an application could request more kernel work isfrom an ISR.WORK QUEUENotice in the above template that kernelState is always checked before itis set.  This is the backbone of the mutual exclusion.  The kernel uses atechnique of work deferral as a means of mutual exclusion.  When kernelStateis TRUE, the function of interest is not invoked directly, but ratherthe work is deferred by enqueueing the job to the kernel work queue.The kernel work queue is emptied by windExit(), (or intExit in the case of anISR entering the kernel first), before loading the context of the appropriatetask.  At the very end of kernel state we lock interrupts, check the workqueue is still empty, and enter a selected task's context.  The deferral ofkernel work is necessary for all kernel routines which are ISR callable.SPECIAL PROBLEMSSome facilities are quite elaborate and require special discussions.  Most areareas still under research or involve some form of tricky code.WATCHDOGSWatchdogs present two ugly problems.  The first problem is the routine wdStart()takes four parameters: the watchdog id, the timeout, the routine, and a routineparameter.  A work queue job only has room for 3 parameters.  So if an ISRcalls wdStart() after interrupting the kernel, we cannot simply defer thework to the work queue.  The solution is to write windWdStart to take onlytwo parameters, the watchdog id, and a timeout.  The routine and parmeterare stored in the watchdog itself.  We're not out of the woods yet, becausewhat if five different ISRs which interrupt the kernel perform a wdStart on thesame watchdog?  Where do we keep all the parameters?  The answer is to simplyclobber the existing routine and parameter with the new routine and newparameter and bump a defer count variable within the watchdog.  Every timewindWdStart() is called as kernel work (or otherwise), the defer count isdecremented.  If the resulting defer count is zero, the watchdog is sorted tothe appropriate timeout in the tick queue.  We know that the timeoutcorresponds to the watchdog routine and parameter resident in the watchdogstructure because the defer count has been decremented as many times as itwas incremented.The second problem is even uglier.  Watchdogs routines may be any arbitraryroutine including kernel routines.  The problem is watchdog routines arenow called from deep within the kernel, in kernel state.  All kernel routinesmade from a watchdog will be deferred to the work queue.  The kicker is thatthere is no limit to the number of watchdogs that can go off in the same tick.If all kernel work is deferred by a limitless number of watchdog routinesexpiring at the same tick, there is a chance that we will overflow the kernelwork queue.  The work queue is implemented as circular queue with a capacityof 64 jobs.  The solution to this problem is to empty the work queue aftereach watchdog routine is called.  We assume that a watchdog routine will nevermake more than 64 kernel calls.Watchdogs are being rethought.  They were not initially considered as partof the kernel, but to make them utilize the tick queue, they got dragged in.As is evident from the problems outlined above, its not a marriage made inheaven.  They are serviceable, but a future version of VxWorks will probablyelect to demote watchdog routines to execute at task level within the contextof a dedicated alarm task.PRIORITY INHERITANCEPriority inversion arises when a higher-priority task is forced to wait anindefinite period of time for the completion of a lower-priority task.Consider the following scenario: T1, T2, and T3 are tasks of high, medium,and low priority, respectively.  T3 has acquired some resource by takingits 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 particularlyproblematic.  After all the resource is non-preemptible.  However, thelow-priority task is vulnerable to preemption by medium-priority tasks; apreempting task, T2, will inhibit T3 from relinquishing the resource.  Thiscondition could persist, blocking T1 for an indefinite period of time.A priority inheritance protocal solves the problem of priority inversion byelevating the priority of T3 to the priority of T1 during the time T1 isblocked on T3.  This protects T3, and indirectly T1, from preemption byT2.  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.  When execution is complete, thetask gives up the resource and returns to its normal, or standard,priority.  Hence, the "inheriting" task is protected from preemption by anyintermediate-priority tasks.Special circumstances apply to nested priority inheritance.  When a taskowns multiple resources guarded from priority inversion, the task's prioritywill `ratchet up' as higher priority tasks contend for the resources.  Forefficiency and simplicity of implementation, task priorities are only allowedto be lowered when a task owns no resources guarded from priority inversion.This rule is useful for situations where a high priority task contends foran owned resource, the priority is inheritted by the owner, but then the highpriority task is deleted.  Strictly speaking, it would be fair game to lowerthe resource owner back to its original priority, but the implemenation isa collosal waste of time and space.  The small price to pay is that tasksmay inherit a priority for a little longer than is actually necessary but Iwon't tell anyone if you won't.DELETION PROBLEMThe deletion problem has two prongs.  The first is that a resourcemay be deleted right ought from under a task.  Nothing protects a taskfrom a semaphore, for example, from being deleted by another task.  We expectthat applications will discipline object deletion to take place safely.  Inthe case of a semaphore, for example, the semaphore should be taken by thedeleter before deletion.  Also note, that the actual invalidation of anobject must be done with mutual exclusion.  Objects which may be utilizedfrom interrupt level must, therefore, protect the object invalidation withinterrupt locks.Object reference counts were considered as an alternative, the difficultylies in the fact that objects are shared in VxWorks without prior consentfrom the operating system.  Some OS require tasks to bind to an object byname before gaining the capability of access.  Object binding does not fitwith current thinking on the matter, but as we exploredistributed/multiprocessor extensions to VxWorks, object id binding mayresurface.The second prong of the deletion problem is harder.  It is possible thata task may be deleted while engaged in some operation on some resource.  Thiscould leave the resource in an unusable, unavailable state.  Tasks are aspecial class of object, an active object which engages passive objects.  Thedeletion of an active object must account for the passive objects currentlyengaged.  We solve this problem in the same way we approach kernel workdeferral.  The deletion of a task is deferred until the task is safe to delete.A deleter will block while a task is protected from deletion, otherwise adeleter might get the false impression that the task deleted is acutually gone.Applications must assist the kernel in determining when a task should beprotected from deletion.  The routine taskSafe() and taskUnsafe() are thebasic operations controlling task deletion protection.  For convenience, amutual exclusion semaphore type is available which has an implicit taskSafe()call on a semTake(), and an implicit taskUnsafe() call on semGive().  Resourcedeletion protection by use of mutual exclusion semaphores is strong steptowards making VxWorks truly capable of dynamic object deletion.FILE STRUCTURE                                     ---------                                     |semBLib|			             |semMLib|                                     |semCLib|                U  S  E  R           |semOLib|  I  N  T  E  R  F  A  C  E   ----------- ----------- --------- -.-.-.-.- ------- ------------ ---------   |kernelLib| |<msgQLib>| |taskLib| |semLib | |wdLib| |<eventLib>| |tickLib|   ----------- ----------- --------- -.-.-.-.- ------- ------------ ---------        |           |          |     |semALib|    |         |           |        |           |          |     ---------    |         |           |        |           |          |         |        |         |           |        \           \          \     ---------    /         /           /         ==========================> |windLib| <========================         |           |          |    ---------    |         |          |         |           |          |                 |         |          |         |           |          |                 |         |          |         \           \          \    ----------   /         /          /          =========================> |windALib| <======================			             |schedLib|			             ----------ROUTINE STRUCTURE			    taskDelete	       taskSpawn                                |              /      |			        |        taskCreat    |                                |            /        |			 taskTerminate  taskInit  taskActivate                                |           |         | taskPrioritySet@* taskDelay* taskDestroy*  |    taskResume@*   |                   |         |          |         |   \  tickAnnounce@*   |         |          |         |       taskSuspend@*    \     \            |         |          |         |          /     \	   \       windDelay windDelete windSpawn windResume    /      \     \	                                               /       \  windTickAnnounce               *             windSuspend        \		                 |  windPriNormalSet--windPrioritySet   windExit	        windPendQPut-semTake*           			 	 |   \	                    \msgQRecv* wdStart@*                               |    \    \                                    |     \         windPendQGet-semGive@*     \----windWdStart                reschedule \                    \msgQSend@*                                         |   \   | wdCancel@*                    @         |    \  |     windPendQFlush-semFlush@*     \------windWdCancel       |         |     \ |              \msgQBroadcast@*			    workQAdd#    |     workQDoWork				     loadContext.CSwindview INSTRUMENTATION------------------------        LEVEL 1 N/A        LEVEL 2                windSpawn causes EVENT_WINDSPAWN                windDelete causes EVENT_WINDDELETE                windSuspend causes EVENT_WINDSUSPEND                windResume causes EVENT_WINDRESUME                windPrioritySet causes EVENT_WINDPRIORITYSETLOWER                windPrioritySet causes EVENT_WINDPRIORITYSETRAISE                windSemDelete causes EVENT_WINDSEMDELETE                windTickAnnounce causes EVENT_WINDTICKUNDELAY                windTickAnnounce causes EVENT_WINDTICKANNOUNCETMRWD                windTickAnnounce causes EVENT_WINDTICKANNOUNCETMRSLC                windTickAnnounce causes EVENT_WINDTICKANNOUNCETMR                windDelay causes EVENT_WINDDELAY                windUndelay causes EVENT_WINDUNDELAY                windWdStart causes EVENT_WINDWDSTART                windWdCancel causes EVENT_WINDWDCANCEL                windPendQGet causes EVENT_WINDPENDQGET                windPendQFlush causes EVENT_WINDPENDQFLUSH                windPendQPut causes EVENT_WINDPENDQPUT                windPendQTerminate causes EVENT_WINDPENDQTERMINATE        LEVEL 3 N/A.CESEE ALSO: "Basic OS", windALib*/#include "vxWorks.h"#include "tickLib.h"#include "taskArchLib.h"#include "semLib.h"#include "smLib.h"#include "wdLib.h"#include "errno.h"#include "qFifoLib.h"#include "qFifoGLib.h"#include "intLib.h"#include "smObjLib.h"#include "private/eventP.h"#include "private/funcBindP.h"#include "private/objLibP.h"#include "private/windLibP.h"#include "private/taskLibP.h"#include "private/workQLibP.h"#include "private/kernelLibP.h"/* global variables */BOOL kernelState;			/* mutex to enter kernel state */BOOL kernelIsIdle;			/* boolean reflecting idle state *//* shared memory objects globals */int  smObjPoolMinusOne;      /* set to smObj pool local address - 1 */int  localToGlobalOffset;    /* localAdrs - globalAdrs *//********************************************************************************* windSpawn - create a task and leave it in the suspend state** This routine inserts the specified tcb into the active queue.* A newly created task is initially in the suspended state.** NOMANUAL*/void windSpawn    (    FAST WIND_TCB *pTcb         /* address of new task's tcb */    )    {#ifdef WV_INSTRUMENTATION    /* windview - level 2 event logging */    EVT_TASK_2 (EVENT_WINDSPAWN, (int) pTcb, pTcb->priority); #endif    Q_PUT (&activeQHead, &pTcb->activeNode, FIFO_KEY_TAIL);	/* in active q*/    }/********************************************************************************* windDelete - delete a task** Delete task and reorganize any queue the task was in.* Assumes that the task owns no inheritance semaphores.** NOMANUAL*/STATUS windDelete    (    FAST WIND_TCB *pTcb         /* address of task's tcb */    )    {    FAST USHORT mask;    FAST int ix;    int  status = OK;		/* status return by windPendQRemove */#ifdef WV_INSTRUMENTATION