windlib.c

VXWORKS源代码

/* 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 #70255
01z,20mar02,bwa  windPendQRemove() now moves task out of the tick Q. (SPR
                 #74673).
01y,18dec00,pes  Correct compiler warnings
01x,29oct97,cth  removed references to scrPad for WV2.0
01w,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 compiled
01t,31jan95,tmk  added OBJ_VERIFY clause to windSemDelete()
	   +rrr
01s,27jan95,ms   windDestroy flushes the right saftey queue now
	   +rrr
01u,02feb94,smb  windPendQFlush no longer causes scratch-pad overflow SPR #2981
01t,24jan94,smb  added tid to EVENT_WINDTICKTIMEOUT
01s,10dec93,smb  added instrumentation
01r,13nov92,dnw  added include of smObjLib.h
01q,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.s
01o,26may92,rrr  the tree shuffle
01n,15oct91,ajm  intCnt change for mips, this must be FIXED correctly soon
01m,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 notice
01l,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 overflow
01h,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.
*/

/*
DESCRIPTION
The VxWorks kernel provides tasking control services to an application.  The
libraries kernelLib, taskLib, semLib, tickLib, and wdLib comprise the kernel
functionality.  This library is internal to the VxWorks kernel and contains
no user callable routines.

INTERNAL
This is a description of the architecture of Wind version 2.0.  The information
here applies to the following libraries: kernelLib, taskLib, semLib, tickLib,
wdLib, schedLib, workQLib, windLib, windALib, semALib, and workQALib.

STATE MACHINE
The kernel is a small state machine.  Each task contains state information in
the 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 in
the aforementioned libraries.  The actual work of changing a task's state and
shuffling it into the appropriate queue is done within this library as a
lower level call to the user routines elsewhere.  For instance taskSuspend()
calls windSuspend().  This decomposition is not purely aesthetic, the separation
is necessary as part of the mutual exclusion method used by the kernel.

MUTUAL EXCLUSION
By the time we arrive in the routines located here, higher level routines have
obtained mutual exclusion to all kernel queues by entering kernel state.  The
routines located here have free reign over any kernel data structure.  Kernel
state is a powerful means of mutual exclusion, unfortunately preemption is
disabled for the duration of kernel state.  High preemptive latency undermines
the reactive latency of a real time system, so it is crucial to use this
mechanism sparingly.  Indeed the basic design philosophy of the kernel is to
keep it as minimal as possible, while still capable of supporting higher level
facilities.

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, contends
for the internal data structures.  An interrupt service routine is the only
possible initiator of additional kernel work.  That is, once a system enters
kernel state the only way an application could request more kernel work is
from an ISR.

WORK QUEUE
Notice in the above template that kernelState is always checked before it
is set.  This is the backbone of the mutual exclusion.  The kernel uses a
technique of work deferral as a means of mutual exclusion.  When kernelState
is TRUE, the function of interest is not invoked directly, but rather
the 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 an
ISR entering the kernel first), before loading the context of the appropriate
task.  At the very end of kernel state we lock interrupts, check the work
queue is still empty, and enter a selected task's context.  The deferral of
kernel work is necessary for all kernel routines which are ISR callable.

SPECIAL PROBLEMS
Some facilities are quite elaborate and require special discussions.  Most are
areas still under research or involve some form of tricky code.

WATCHDOGS
Watchdogs present two ugly problems.  The first problem is the routine wdStart()
takes four parameters: the watchdog id, the timeout, the routine, and a routine
parameter.  A work queue job only has room for 3 parameters.  So if an ISR
calls wdStart() after interrupting the kernel, we cannot simply defer the
work to the work queue.  The solution is to write windWdStart to take only
two parameters, the watchdog id, and a timeout.  The routine and parmeter
are stored in the watchdog itself.  We're not out of the woods yet, because
what if five different ISRs which interrupt the kernel perform a wdStart on the
same watchdog?  Where do we keep all the parameters?  The answer is to simply
clobber the existing routine and parameter with the new routine and new
parameter and bump a defer count variable within the watchdog.  Every time
windWdStart() is called as kernel work (or otherwise), the defer count is
decremented.  If the resulting defer count is zero, the watchdog is sorted to
the appropriate timeout in the tick queue.  We know that the timeout
corresponds to the watchdog routine and parameter resident in the watchdog
structure because the defer count has been decremented as many times as it
was incremented.

The second problem is even uglier.  Watchdogs routines may be any arbitrary
routine including kernel routines.  The problem is watchdog routines are
now called from deep within the kernel, in kernel state.  All kernel routines
made from a watchdog will be deferred to the work queue.  The kicker is that
there 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 routines
expiring at the same tick, there is a chance that we will overflow the kernel
work queue.  The work queue is implemented as circular queue with a capacity
of 64 jobs.  The solution to this problem is to empty the work queue after
each watchdog routine is called.  We assume that a watchdog routine will never
make more than 64 kernel calls.

Watchdogs are being rethought.  They were not initially considered as part
of 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 in
heaven.  They are serviceable, but a future version of VxWorks will probably
elect to demote watchdog routines to execute at task level within the context
of a dedicated alarm task.

PRIORITY INHERITANCE
Priority inversion arises when a higher-priority task is forced to wait an
indefinite 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 taking
its associated semaphore.  When T1 preempts T3 and contends for the
resource by taking the same semaphore, it becomes blocked.  If we could be
assured that T1 would be blocked no longer than the time it normally takes
T3 to finish with the resource, the situation would not be particularly
problematic.  After all the resource is non-preemptible.  However, the
low-priority task is vulnerable to preemption by medium-priority tasks; a
preempting task, T2, will inhibit T3 from relinquishing the resource.  This
condition could persist, blocking T1 for an indefinite period of time.

A priority inheritance protocal solves the problem of priority inversion by
elevating the priority of T3 to the priority of T1 during the time T1 is
blocked on T3.  This protects T3, and indirectly T1, from preemption by
T2.  Stated more generally, the priority inheritance protocol assures that
a task which owns a resource will execute at the priority of the highest
priority task blocked on that resource.  When execution is complete, the
task gives up the resource and returns to its normal, or standard,
priority.  Hence, the "inheriting" task is protected from preemption by any
intermediate-priority tasks.

Special circumstances apply to nested priority inheritance.  When a task
owns multiple resources guarded from priority inversion, the task's priority
will `ratchet up' as higher priority tasks contend for the resources.  For
efficiency and simplicity of implementation, task priorities are only allowed
to be lowered when a task owns no resources guarded from priority inversion.
This rule is useful for situations where a high priority task contends for
an owned resource, the priority is inheritted by the owner, but then the high
priority task is deleted.  Strictly speaking, it would be fair game to lower
the resource owner back to its original priority, but the implemenation is
a collosal waste of time and space.  The small price to pay is that tasks
may inherit a priority for a little longer than is actually necessary but I
won't tell anyone if you won't.

DELETION PROBLEM
The deletion problem has two prongs.  The first is that a resource
may be deleted right ought from under a task.  Nothing protects a task
from a semaphore, for example, from being deleted by another task.  We expect
that applications will discipline object deletion to take place safely.  In
the case of a semaphore, for example, the semaphore should be taken by the
deleter before deletion.  Also note, that the actual invalidation of an
object must be done with mutual exclusion.  Objects which may be utilized
from interrupt level must, therefore, protect the object invalidation with
interrupt locks.

Object reference counts were considered as an alternative, the difficulty
lies in the fact that objects are shared in VxWorks without prior consent
from the operating system.  Some OS require tasks to bind to an object by
name before gaining the capability of access.  Object binding does not fit
with current thinking on the matter, but as we explore
distributed/multiprocessor extensions to VxWorks, object id binding may
resurface.

The second prong of the deletion problem is harder.  It is possible that
a task may be deleted while engaged in some operation on some resource.  This
could leave the resource in an unusable, unavailable state.  Tasks are a
special class of object, an active object which engages passive objects.  The
deletion of an active object must account for the passive objects currently
engaged.  We solve this problem in the same way we approach kernel work
deferral.  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 a
deleter might get the false impression that the task deleted is acutually gone.
Applications must assist the kernel in determining when a task should be
protected from deletion.  The routine taskSafe() and taskUnsafe() are the
basic operations controlling task deletion protection.  For convenience, a
mutual exclusion semaphore type is available which has an implicit taskSafe()
call on a semTake(), and an implicit taskUnsafe() call on semGive().  Resource
deletion protection by use of mutual exclusion semaphores is strong step
towards 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

.CS

windview 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
.CE

SEE 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