491 lines
12 KiB
C
491 lines
12 KiB
C
/*
|
||
|
||
Copyright (c) 1992 Microsoft Corporation
|
||
|
||
Module Name:
|
||
|
||
scavengr.c
|
||
|
||
Abstract:
|
||
|
||
This file implements the scavenger queue management interface.
|
||
|
||
Author:
|
||
|
||
Jameel Hyder (microsoft!jameelh)
|
||
|
||
|
||
Revision History:
|
||
25 Jun 1992 Initial Version
|
||
|
||
Notes: Tab stop: 4
|
||
--*/
|
||
|
||
#define _SCAVENGER_LOCALS
|
||
#define FILENUM FILE_SCAVENGR
|
||
|
||
#include <afp.h>
|
||
#include <scavengr.h>
|
||
#include <client.h>
|
||
|
||
#ifdef ALLOC_PRAGMA
|
||
#pragma alloc_text( INIT, AfpScavengerInit)
|
||
#pragma alloc_text( PAGE, AfpScavengerDeInit)
|
||
#endif
|
||
|
||
/*** AfpScavengerInit
|
||
*
|
||
* Initialize the scavenger system. This consists of a queue protected by a
|
||
* spin lock and timer coupled to a DPC. The scavenger accepts requests to
|
||
* schedule a worker after N units of time.
|
||
*/
|
||
NTSTATUS
|
||
AfpScavengerInit(
|
||
VOID
|
||
)
|
||
{
|
||
BOOLEAN TimerStarted;
|
||
LARGE_INTEGER TimerValue;
|
||
|
||
KeInitializeTimer(&afpScavengerTimer);
|
||
INITIALIZE_SPIN_LOCK(&afpScavengerLock);
|
||
KeInitializeDpc(&afpScavengerDpc, afpScavengerDpcRoutine, NULL);
|
||
TimerValue.QuadPart = AFP_SCAVENGER_TIMER_TICK;
|
||
TimerStarted = KeSetTimer(&afpScavengerTimer,
|
||
TimerValue,
|
||
&afpScavengerDpc);
|
||
ASSERT(!TimerStarted);
|
||
|
||
return STATUS_SUCCESS;
|
||
}
|
||
|
||
|
||
/*** AfpScavengerDeInit
|
||
*
|
||
* De-Initialize the scavenger system. Just cancel the timer.
|
||
*/
|
||
VOID
|
||
AfpScavengerDeInit(
|
||
VOID
|
||
)
|
||
{
|
||
KeCancelTimer(&afpScavengerTimer);
|
||
}
|
||
|
||
|
||
/*** AfpScavengerEnqueue
|
||
*
|
||
* Here is a thesis on the code that follows.
|
||
*
|
||
* The scavenger events are maintained as a list which the scavenger thread
|
||
* looks at every timer tick. The list is maintained in such a way that only
|
||
* the head of the list needs to be updated every tick i.e. the entire list
|
||
* is never scanned. The way this is achieved is by keeping delta times
|
||
* relative to the previous entry.
|
||
*
|
||
* Every timer tick, the relative time at the head of the list is decremented.
|
||
* When that goes to ZERO, the head of the list is unlinked and dispatched.
|
||
*
|
||
* To give an example, we have the following events queued at time slots
|
||
* X Schedule A after 10 ticks.
|
||
* X+3 Schedule B after 5 ticks.
|
||
* X+5 Schedule C after 4 ticks.
|
||
* X+8 Schedule D after 6 ticks.
|
||
*
|
||
* So A will schedule at X+10, B at X+8 (X+3+5), C at X+9 (X+5+4) and
|
||
* D at X+14 (X+8+6).
|
||
*
|
||
* The above example covers all the situations.
|
||
*
|
||
* - NULL List.
|
||
* - Inserting at head of list.
|
||
* - Inserting in the middle of the list.
|
||
* - Appending to the list tail.
|
||
*
|
||
* The list will look as follows.
|
||
*
|
||
* BEFORE AFTER
|
||
* ------ -----
|
||
*
|
||
* X Head -->| Head -> A(10) ->|
|
||
* A(10)
|
||
*
|
||
* X+3 Head -> A(7) ->| Head -> B(5) -> A(2) ->|
|
||
* B(5)
|
||
*
|
||
* X+5 Head -> B(3) -> A(2) ->| Head -> B(3) -> C(1) -> A(1) ->|
|
||
* C(4)
|
||
*
|
||
* X+8 Head -> C(1) -> A(1) ->| Head -> C(1) -> A(1) -> D(4) ->|
|
||
* D(6)
|
||
*
|
||
* The granularity is one tick.
|
||
*
|
||
* LOCKS_ASSUMED: AfpScavengerLock (SPIN)
|
||
*/
|
||
VOID
|
||
afpScavengerEnqueue(
|
||
IN PSCAVENGERLIST pListNew
|
||
)
|
||
{
|
||
PSCAVENGERLIST pList, *ppList;
|
||
LONG DeltaTime = pListNew->scvgr_AbsTime;
|
||
|
||
// The DeltaTime is adjusted in every pass of the loop to reflect the
|
||
// time after the previous entry that the new entry will schedule.
|
||
for (ppList = &afpScavengerList;
|
||
(pList = *ppList) != NULL;
|
||
ppList = &pList->scvgr_Next)
|
||
{
|
||
if (DeltaTime <= pList->scvgr_RelDelta)
|
||
{
|
||
pList->scvgr_RelDelta -= DeltaTime;
|
||
break;
|
||
}
|
||
DeltaTime -= pList->scvgr_RelDelta;
|
||
}
|
||
|
||
pListNew->scvgr_RelDelta = DeltaTime;
|
||
pListNew->scvgr_Next = pList;
|
||
*ppList = pListNew;
|
||
}
|
||
|
||
|
||
/*** AfpScavengerScheduleEvent
|
||
*
|
||
* Insert an event in the scavenger event list. If the list is empty, then
|
||
* fire off a timer. The time is specified in ticks. Each tick is currently
|
||
* ONE SECOND. It may not be negative.
|
||
*
|
||
* The granularity is one tick.
|
||
*/
|
||
NTSTATUS
|
||
AfpScavengerScheduleEvent(
|
||
IN SCAVENGER_ROUTINE Worker, // Routine to invoke when time expires
|
||
IN PVOID pContext, // Context to pass to the routine
|
||
IN LONG DeltaTime, // Schedule after this much time
|
||
IN BOOLEAN fQueue // If TRUE, then worker must be queued
|
||
)
|
||
{
|
||
PSCAVENGERLIST pList = NULL;
|
||
KIRQL OldIrql;
|
||
NTSTATUS Status = STATUS_SUCCESS;
|
||
|
||
// Negative DeltaTime is invalid. ZERO is valid which implies immediate action
|
||
ASSERT (DeltaTime >= 0);
|
||
|
||
do
|
||
{
|
||
pList = (PSCAVENGERLIST)AfpAllocNonPagedMemory(sizeof(SCAVENGERLIST));
|
||
if (pList == NULL)
|
||
{
|
||
DBGPRINT(DBG_COMP_SCVGR, DBG_LEVEL_ERR,
|
||
("AfpScavengerScheduleEvent: malloc Failed\n"));
|
||
Status = STATUS_INSUFFICIENT_RESOURCES;
|
||
break;
|
||
}
|
||
|
||
AfpInitializeWorkItem(&pList->scvgr_WorkItem,
|
||
afpScavengerWorker,
|
||
pList);
|
||
pList->scvgr_Worker = Worker;
|
||
pList->scvgr_Context = pContext;
|
||
pList->scvgr_AbsTime = DeltaTime;
|
||
pList->scvgr_fQueue = fQueue;
|
||
|
||
if (DeltaTime == 0)
|
||
{
|
||
ASSERT (fQueue);
|
||
AfpQueueWorkItem(&pList->scvgr_WorkItem);
|
||
break;
|
||
}
|
||
|
||
if (!afpScavengerStopped)
|
||
{
|
||
ACQUIRE_SPIN_LOCK(&afpScavengerLock, &OldIrql);
|
||
|
||
//
|
||
// due to an assumption made elsewhere, it's necessary to check
|
||
// this again after holding the spinlock!
|
||
//
|
||
if (!afpScavengerStopped)
|
||
{
|
||
afpScavengerEnqueue(pList);
|
||
RELEASE_SPIN_LOCK(&afpScavengerLock, OldIrql);
|
||
}
|
||
else
|
||
{
|
||
DBGPRINT(DBG_COMP_SCVGR, DBG_LEVEL_ERR,
|
||
("AfpScavengerScheduleEvent: Called after Flush !!\n"));
|
||
|
||
RELEASE_SPIN_LOCK(&afpScavengerLock, OldIrql);
|
||
AfpFreeMemory(pList);
|
||
Status = STATUS_UNSUCCESSFUL;
|
||
}
|
||
}
|
||
|
||
} while (False);
|
||
|
||
return Status;
|
||
}
|
||
|
||
|
||
|
||
/*** AfpScavengerKillEvent
|
||
*
|
||
* Kill an event that was previously scheduled.
|
||
*/
|
||
BOOLEAN
|
||
AfpScavengerKillEvent(
|
||
IN SCAVENGER_ROUTINE Worker, // Routine that was scheduled
|
||
IN PVOID pContext // Context
|
||
)
|
||
{
|
||
PSCAVENGERLIST pList, *ppList;
|
||
KIRQL OldIrql;
|
||
|
||
ACQUIRE_SPIN_LOCK(&afpScavengerLock, &OldIrql);
|
||
|
||
// The DeltaTime is adjusted in every pass of the loop to reflect the
|
||
// time after the previous entry that the new entry will schedule.
|
||
for (ppList = &afpScavengerList;
|
||
(pList = *ppList) != NULL;
|
||
ppList = &pList->scvgr_Next)
|
||
{
|
||
if ((pList->scvgr_Worker == Worker) &&
|
||
(pList->scvgr_Context == pContext))
|
||
{
|
||
*ppList = pList->scvgr_Next;
|
||
if (pList->scvgr_Next != NULL)
|
||
{
|
||
pList->scvgr_Next->scvgr_RelDelta += pList->scvgr_RelDelta;
|
||
}
|
||
break;
|
||
}
|
||
}
|
||
|
||
RELEASE_SPIN_LOCK(&afpScavengerLock, OldIrql);
|
||
|
||
if (pList != NULL)
|
||
AfpFreeMemory(pList);
|
||
|
||
return (pList != NULL);
|
||
}
|
||
|
||
|
||
/*** afpScavengerDpcRoutine
|
||
*
|
||
* This is called in at DISPATCH_LEVEL when the timer expires. The entry at
|
||
* the head of the list is decremented and if ZERO unlinked and queued to the
|
||
* worker. If the list is non-empty, the timer is fired again.
|
||
*/
|
||
LOCAL VOID
|
||
afpScavengerDpcRoutine(
|
||
IN PKDPC pKDpc,
|
||
IN PVOID pContext,
|
||
IN PVOID SystemArgument1,
|
||
IN PVOID SystemArgument2
|
||
)
|
||
{
|
||
PSCAVENGERLIST pList;
|
||
AFPSTATUS Status;
|
||
BOOLEAN TimerStarted;
|
||
LARGE_INTEGER TimerValue;
|
||
#ifdef PROFILING
|
||
TIME TimeS, TimeE;
|
||
DWORD NumDispatched = 0;
|
||
|
||
AfpGetPerfCounter(&TimeS);
|
||
#endif
|
||
|
||
|
||
AfpSecondsSinceEpoch++;
|
||
|
||
if (afpScavengerStopped)
|
||
{
|
||
DBGPRINT(DBG_COMP_SCVGR, DBG_LEVEL_ERR,
|
||
("afpScavengerDpcRoutine: Entered after flush !!!\n"));
|
||
return;
|
||
}
|
||
|
||
if (afpScavengerList != NULL)
|
||
{
|
||
ACQUIRE_SPIN_LOCK_AT_DPC(&afpScavengerLock);
|
||
|
||
if (afpScavengerList->scvgr_RelDelta != 0)
|
||
(afpScavengerList->scvgr_RelDelta)--;
|
||
|
||
// We should never be here if we have no work to do
|
||
while (afpScavengerList != NULL)
|
||
{
|
||
// Dispatch all entries that are ready to go
|
||
if (afpScavengerList->scvgr_RelDelta == 0)
|
||
{
|
||
pList = afpScavengerList;
|
||
afpScavengerList = pList->scvgr_Next;
|
||
DBGPRINT(DBG_COMP_SCVGR, DBG_LEVEL_INFO,
|
||
("afpScavengerDpcRoutine: Dispatching %lx\n",
|
||
pList->scvgr_WorkItem.wi_Worker));
|
||
|
||
// Release spin lock as the caller might call us back
|
||
RELEASE_SPIN_LOCK_FROM_DPC(&afpScavengerLock);
|
||
|
||
Status = AFP_ERR_QUEUE;
|
||
if (!pList->scvgr_fQueue)
|
||
{
|
||
Status = (*pList->scvgr_Worker)(pList->scvgr_Context);
|
||
#ifdef PROFILING
|
||
NumDispatched++;
|
||
#endif
|
||
}
|
||
|
||
ACQUIRE_SPIN_LOCK_AT_DPC(&afpScavengerLock);
|
||
|
||
if (Status == AFP_ERR_QUEUE)
|
||
{
|
||
DBGPRINT(DBG_COMP_SCVGR, DBG_LEVEL_INFO,
|
||
("afpScavengerDpcRoutine: Queueing %lx\n",
|
||
pList->scvgr_WorkItem.wi_Worker));
|
||
AfpQueueWorkItem(&pList->scvgr_WorkItem);
|
||
}
|
||
else if (Status == AFP_ERR_REQUEUE)
|
||
{
|
||
afpScavengerEnqueue(pList);
|
||
}
|
||
else AfpFreeMemory(pList);
|
||
}
|
||
else break;
|
||
}
|
||
|
||
RELEASE_SPIN_LOCK_FROM_DPC(&afpScavengerLock);
|
||
}
|
||
|
||
TimerValue.QuadPart = AFP_SCAVENGER_TIMER_TICK;
|
||
TimerStarted = KeSetTimer(&afpScavengerTimer,
|
||
TimerValue,
|
||
&afpScavengerDpc);
|
||
ASSERT(!TimerStarted);
|
||
|
||
#ifdef PROFILING
|
||
AfpGetPerfCounter(&TimeE);
|
||
ACQUIRE_SPIN_LOCK_AT_DPC(&AfpStatisticsLock);
|
||
AfpServerProfile->perf_ScavengerCount += NumDispatched;
|
||
AfpServerProfile->perf_ScavengerTime.QuadPart +=
|
||
(TimeE.QuadPart - TimeS.QuadPart);
|
||
RELEASE_SPIN_LOCK_FROM_DPC(&AfpStatisticsLock);
|
||
#endif
|
||
}
|
||
|
||
|
||
/*** AfpScavengerFlushAndStop
|
||
*
|
||
* Force all entries in the scavenger queue to be dispatched immediately. No
|
||
* more queue'ing of scavenger routines is permitted after this. The scavenger
|
||
* essentially shuts down. Callable only in the worker context.
|
||
*/
|
||
VOID
|
||
AfpScavengerFlushAndStop(
|
||
VOID
|
||
)
|
||
{
|
||
PSCAVENGERLIST pList;
|
||
KIRQL OldIrql;
|
||
|
||
ASSERT (KeGetCurrentIrql() < DISPATCH_LEVEL);
|
||
|
||
DBGPRINT(DBG_COMP_SCVGR, DBG_LEVEL_INFO,
|
||
("afpScavengerFlushAndStop: Entered\n"));
|
||
|
||
ASSERT (KeGetCurrentIrql() < DISPATCH_LEVEL);
|
||
|
||
ACQUIRE_SPIN_LOCK(&afpScavengerLock, &OldIrql);
|
||
|
||
afpScavengerStopped = True;
|
||
|
||
KeCancelTimer(&afpScavengerTimer);
|
||
|
||
if (afpScavengerList != NULL)
|
||
{
|
||
// Dispatch all entries right away
|
||
while (afpScavengerList != NULL)
|
||
{
|
||
AFPSTATUS Status;
|
||
|
||
pList = afpScavengerList;
|
||
afpScavengerList = pList->scvgr_Next;
|
||
|
||
// Call the worker with spin-lock held since they expect to be
|
||
// called at DPC. We are safe since if the worker tries to
|
||
// call AfpScavengerScheduleEvent(), we'll not try to re-acquire
|
||
// the lock as afpScavengerStopped is True.
|
||
DBGPRINT(DBG_COMP_SCVGR, DBG_LEVEL_INFO,
|
||
("afpScavengerFlushAndStop: Dispatching %lx\n",
|
||
pList->scvgr_WorkItem.wi_Worker));
|
||
|
||
if (!(pList->scvgr_fQueue))
|
||
Status = (*pList->scvgr_Worker)(pList->scvgr_Context);
|
||
|
||
if (pList->scvgr_fQueue ||
|
||
(Status == AFP_ERR_QUEUE))
|
||
{
|
||
// Well do it the hard way, if the worker insists on working
|
||
// at non DISPACTH level.
|
||
RELEASE_SPIN_LOCK(&afpScavengerLock, OldIrql);
|
||
(*pList->scvgr_Worker)(pList->scvgr_Context);
|
||
ACQUIRE_SPIN_LOCK(&afpScavengerLock, &OldIrql);
|
||
}
|
||
AfpFreeMemory(pList);
|
||
}
|
||
}
|
||
RELEASE_SPIN_LOCK(&afpScavengerLock, OldIrql);
|
||
}
|
||
|
||
|
||
/*** AfpScavengerWorker
|
||
*
|
||
* This gets invoked when the scavenger Dpc queues up the routine.
|
||
*/
|
||
LOCAL VOID FASTCALL
|
||
afpScavengerWorker(
|
||
IN PSCAVENGERLIST pList
|
||
)
|
||
{
|
||
AFPSTATUS Status;
|
||
KIRQL OldIrql;
|
||
#ifdef PROFILING
|
||
TIME TimeS, TimeE;
|
||
|
||
AfpGetPerfCounter(&TimeS);
|
||
#endif
|
||
|
||
ASSERT (KeGetCurrentIrql() < DISPATCH_LEVEL);
|
||
|
||
// Call the worker routine
|
||
Status = (*pList->scvgr_Worker)(pList->scvgr_Context);
|
||
|
||
ASSERT (Status != AFP_ERR_QUEUE);
|
||
|
||
#ifdef PROFILING
|
||
AfpGetPerfCounter(&TimeE);
|
||
ACQUIRE_SPIN_LOCK(&AfpStatisticsLock, &OldIrql);
|
||
AfpServerProfile->perf_ScavengerCount++;
|
||
AfpServerProfile->perf_ScavengerTime.QuadPart +=
|
||
(TimeE.QuadPart - TimeS.QuadPart);
|
||
RELEASE_SPIN_LOCK(&AfpStatisticsLock, OldIrql);
|
||
#endif
|
||
|
||
if (Status == AFP_ERR_REQUEUE)
|
||
{
|
||
ACQUIRE_SPIN_LOCK(&afpScavengerLock, &OldIrql);
|
||
afpScavengerEnqueue(pList);
|
||
RELEASE_SPIN_LOCK(&afpScavengerLock, OldIrql);
|
||
}
|
||
else
|
||
{
|
||
ASSERT (NT_SUCCESS(Status));
|
||
AfpFreeMemory(pList);
|
||
}
|
||
}
|
||
|
||
|
||
|