pback.c

Vitual Ring Routing 管你知不知道

// -*- mode: C++; tab-width: 4; indent-tabs-mode: nil -*- (for GNU Emacs)
//
// (c) Microsoft Corporation. All rights reserved. 
//
// This file is part of the Microsoft Virtual Ring Routing distribution.
// You should have received a copy of the Microsoft Research Shared Source
// license agreement (MSR-SSLA) for this software; see the file "license.txt".
// If not, please see http://research.microsoft.com/vrr/license.htm,
// or write to Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399.
//
// This file is derived from the Microsoft Research Mesh Connectivity Layer,
// available under the MSR-SSLA license, and downloadable from
// http://research.microsoft.com/mesh/.
//
// Abstract:
//
// Piggy-backing module. General mechanism for sending VRR options
// at a later time, hopefully by piggy-backing on another packet
// that is going in the right direction.
//

#include "headers.h"

//* PbackInit
//
//  Initializes the piggy-back data structures.
//
void
PbackInit(MiniportAdapter *VA)
{
    PbackCache *PCache = &VA->PCache;

    KeInitializeSpinLock(&PCache->Lock);
    VRRASSERT(PCache->List == NULL);
}

//* PbackCleanup
//
//  Cleans up the piggy-back data structures.
//
void
PbackCleanup(MiniportAdapter *VA)
{
    PbackCache *PCache = &VA->PCache;
    PbackOption *PO;

    while ((PO = PCache->List) != NULL) {
        PCache->List = PO->Next;
        VrrKdPrint("PbackCleanup: free pcache entry",NULL,NULL);
        ExFreePool(PO->Opt);
        ExFreePool(PO);
    }
}

//* PbackResetStatistics
//
//  Resets all counters and statistics gathering for the piggy-backing module.
//
void
PbackResetStatistics(MiniportAdapter *VA)
{
    PbackCache *PCache = &VA->PCache;
    KIRQL OldIrql;

    KeAcquireSpinLock(&PCache->Lock, &OldIrql);
    PCache->HighWater = PCache->Number;
    PCache->AckMaxDupTime = 0;
    PCache->CountPbackReply = 0;
    PCache->CountAloneReply = 0;
    PCache->CountPbackError = 0;
    PCache->CountAloneError = 0;
    PCache->CountPbackInfo = 0;
    PCache->CountAloneInfo = 0;
    KeReleaseSpinLock(&PCache->Lock, OldIrql);
}

//* MsgQueueMessage
//
//  Enqueue a message with a specified transmission deadline.
//  Takes ownership of the message memory.
//
void
MsgQueueMessage(
    MiniportAdapter *VA,
    VirtualAddress Dest,       // May point into the option.
    InternalOption *Opt,
    VRRIf LocIF,
    VRRIf RemIF,
    Time Timeout,              // Relative.
    TxToken *SRToken)
{
    PbackCache *PCache = &VA->PCache;
    PbackOption *PO, *NewPO, **PrevPO;
    Time Now = KeQueryInterruptTime();
    KIRQL OldIrql;
    TxToken TokenBuff;
    TxToken *Token = &TokenBuff;
    uint DelayMS = TIME_TO_MS(Timeout);

    //
    // If you add another option type that can be piggy-backed,
    // you must also update PbackAddOptionToPacket.
    //

    //
    // Obtain TxToken to store in PO.
    //
    switch (Opt->Opt.optionType) {

    case VRR_OPTION_TYPE_SETUPREQ:
        {
            //
            // Caller supplies TxToken, ref possible SRcAntiRoute.
            //
            VRRASSERT(SRToken != NULL);
            VRRASSERT(! IsNullTxToken(SRToken));
            Token = SRToken;
            break;
        }
    case VRR_OPTION_TYPE_ACK:
    case VRR_OPTION_TYPE_SETUP:
    case VRR_OPTION_TYPE_TEARDOWN:
        //
        // The NextHop is fixed and must not be changed by FNH.
        //
        VRRASSERT(SRToken == NULL);
        if (GetPhysNeighborTxToken(VA,Dest,LocIF,RemIF,Token,VRR_NCE_STATE_LINKED)==FALSE) {
            //
            // Dest was selected because it was a physical neighbor
            // en route to Setup->Dest (i.e. EndpointB or its proxy).
            // It must be that Dest is no longer a physical neighbor.
            //
            // If message is a Setup our own neighbor detection should 
            // detect a link failure and initiate TD with respect to the
            // trail of RTE that saw this Setup, so we can just drop it.
            //
#if DBG
            if (Opt->Opt.optionType == VRR_OPTION_TYPE_ACK) {
                Acknowledgement *Ack = (Acknowledgement *)&Opt->Opt;
                InterlockedIncrement((PLONG)&VA->CountMsQDropCritical);
                VrrTrace(VA,3,"MQ:AK=Drop",Ack->from,Token->NextVAddress,Ack->to,"id",Ack->identification,NULL,0);
            }
            if (Opt->Opt.optionType == VRR_OPTION_TYPE_SETUP) {
                VrrSetup *Setup = (VrrSetup *)&Opt->Opt;
                InterlockedIncrement((PLONG)&VA->CountMsQDropCritical);
                VrrTrace(VA,3,"MQ:SU=Drop",Setup->A,Token->NextVAddress,Setup->B,
                       "Pid",RtlUlongByteSwap(Setup->PathId),"FrameSeqNo",RtlUlongByteSwap(Setup->FrameSeqNo));
            }
            if (Opt->Opt.optionType == VRR_OPTION_TYPE_TEARDOWN) {
                VrrTearDown *TD = (VrrTearDown *)&Opt->Opt;
                int NumPId = RtlUlongByteSwap(TD->NumGlobalPathId);
                int i;
                InterlockedIncrement((PLONG)&VA->CountMsQDropCritical);
                for (i = 0; i < NumPId; i++) {
                    VrrTrace(VA,3,"MQ:TD=Drop",TD->Source,Token->NextVAddress,TD->PId[i].Address,
                           "Pid",RtlUlongByteSwap(TD->PId[i].PathId),NULL,0);
                }
            }
#endif
            ExFreePool(Opt);
            Timeout = MAXTIME; // No need to reschedule for dup SR.
            goto Return;

        }
        break;

    default:
        {
            VrrKdPrint("MsgQMsg: unexpected message type",NULL,Dest);
            VRRASSERT(FALSE);
            ExFreePool(Opt);
            Timeout = MAXTIME; // No need to reschedule for dup SR.
            goto Return;
        }

    } // switch()

    KeAcquireSpinLock(&PCache->Lock, &OldIrql);

    //
    // Filter and discard duplicate SR messages.
    //
    // Note: together with SR tx delay this throttles rate at which
    // we can generate duplicate SR for a given destination.
    //
    // Note: if we decide to filter other message types we must worry
    // about whether to keep the earlier or later duplicate, and whether
    // any messages between them in the queue order affect the semantics.
    // With SR the source will regen automatically if needed.
    //
    for (PO = PCache->List; PO != NULL; PO = PO->Next) {
        switch (Opt->Opt.optionType) {
        case VRR_OPTION_TYPE_SETUPREQ:
            if (PO->Opt->Opt.optionType == Opt->Opt.optionType)
            if (PO->Opt->Opt.optDataLen == Opt->Opt.optDataLen)
            if (RtlEqualMemory(PO->Opt->Opt.payload, Opt->Opt.payload, Opt->Opt.optDataLen)) {
                VrrSetupReq *SR = (VrrSetupReq *)&Opt->Opt;
                VrrTrace(VA,2,"MQ:SR=Drop(DupGen)",SR->Source,Token->NextVAddress,SR->Dest,NULL,0,"FrameSeqNo",RtlUlongByteSwap(SR->FrameSeqNo));
                ExFreePool(Opt);
                Timeout = MAXTIME; // No need to reschedule for dup SR.
                goto UnlockAndReturn;
            }
            break;
        default:
            break;
        }
    }

    NewPO = ExAllocatePool(NonPagedPool, sizeof *NewPO);
    if (NewPO == NULL) {
        //
        // We can't send the message but we do need to free it.
        //
        if (Opt->Opt.optionType == VRR_OPTION_TYPE_ACK ||
            Opt->Opt.optionType == VRR_OPTION_TYPE_SETUP ||
            Opt->Opt.optionType == VRR_OPTION_TYPE_TEARDOWN) {
            InterlockedIncrement((PLONG)&VA->CountMsQDropCritical);
        }
        ExFreePool(Opt);
        Timeout = MAXTIME; // No need to reschedule.
        goto UnlockAndReturn;
    }

    //
    // Initialize the piggyback option.
    //
    RtlCopyMemory(NewPO->Dest, Dest, SR_ADDR_LEN);
    NewPO->Opt = Opt;
    RtlCopyMemory(&NewPO->Token,Token,sizeof(TxToken));

    //
    // Convert the relative timeout to absolute.
    //
    Timeout = Now + Timeout;
    NewPO->Timeout = Timeout;

    //
    // Add the message to the message queue.
    // The queue is sorted by timeout, from soonest to latest.
    //
    PrevPO = &PCache->List;
    while ((PO = *PrevPO) != NULL) {
        if (Timeout < PO->Timeout)
            break;
        PrevPO = &PO->Next;
        Timeout = MAXTIME; // No need to reschedule.
    }
    NewPO->Next = PO;
    *PrevPO = NewPO;

    if (++PCache->Number > PCache->HighWater)
        PCache->HighWater = PCache->Number;

#if DBG
    if (Opt->Opt.optionType == VRR_OPTION_TYPE_SETUP) {
        VrrSetup *Setup = (VrrSetup *)&Opt->Opt;
        VrrTrace(VA,3,"MQ:SU=2MQ_",Setup->A,Token->NextVAddress,Setup->B,
               "Pid",RtlUlongByteSwap(Setup->PathId),"DelayMS",DelayMS);
    }
    else if (Opt->Opt.optionType == VRR_OPTION_TYPE_TEARDOWN) {
        VrrTearDown *TD = (VrrTearDown *)&Opt->Opt;
        int NumPId = RtlUlongByteSwap(TD->NumGlobalPathId);
        int i;

        for (i = 0; i < NumPId; i++)
            VrrTrace(VA,3,"MQ:TD=2MQ_",TD->Source,Token->NextVAddress,TD->PId[i].Address,"Pid",
                   RtlUlongByteSwap(TD->PId[i].PathId),"DelayMS",DelayMS);
    }
    else if (Opt->Opt.optionType == VRR_OPTION_TYPE_ACK) {
        Acknowledgement *Ack = (Acknowledgement *)&Opt->Opt;
        VrrTrace(VA,3,"MQ:AK=2MQ_",Ack->from,Token->NextVAddress,Ack->to,"SeqNo",Ack->identification,"DelayMS",DelayMS);
    }
    else if (Opt->Opt.optionType == VRR_OPTION_TYPE_SETUPREQ) {
        VrrSetupReq *SR = (VrrSetupReq *)&Opt->Opt;
        VrrTrace(VA,3,"MQ:SR=2MQ_",SR->Source,Token->NextVAddress,SR->Dest,
               "FrameSeqNo",RtlUlongByteSwap(SR->FrameSeqNo),"DelayMS",DelayMS);
    }

#endif

UnlockAndReturn:
    KeReleaseSpinLock(&PCache->Lock, OldIrql);
Return:

    //
    // If necessary, reschedule the next timeout.
    //
    if (Timeout != MAXTIME)
        MiniportRescheduleTimeout(VA, Now, Timeout);
}

//* MsgMoveMessageToSRP
//
//  Helper for MsgLoadSRPfromPCache and MessageTimeout.
//  Adds a VRR option to an SRPacket.
//
static void
MsgMoveMessageToSRP(
    MiniportAdapter *VA,
    PbackCache *PCache,
    SRPacket *SRP,
    InternalOption *Opt)
{
    InternalOption **Field;

    switch (Opt->Opt.optionType) {
    case VRR_OPTION_TYPE_ACK: {
        Acknowledgement *Ack = (Acknowledgement *)&Opt->Opt;
        Field = (InternalOption **) &SRP->ack;
        VrrTrace(VA,3,"MQ:AK=2SRP",Ack->from,SRP->Token.NextVAddress,Ack->to,
                 "id",Ack->identification,"FrameSeqNo",SRP->FrameSeqNo);
        break;
    }
    case VRR_OPTION_TYPE_SETUP: {
        VrrSetup *Setup = (VrrSetup *)&Opt->Opt;
        Field = (InternalOption **) &SRP->VrrSetup;
        VrrTrace(VA,3,"MQ:SU=2SRP",Setup->A,SRP->Token.NextVAddress,Setup->B,
                 "Pid",RtlUlongByteSwap(Setup->PathId),"FrameSeqNo",SRP->FrameSeqNo);
        UpdatePacketIndex(VA, Setup->A, RtlUlongByteSwap(Setup->FrameSeqNo), Setup->HopCount++,
                  SRP->Source, SRP->Dest, SRP->Token.LocIF, VRR_OPTION_TYPE_SETUP);
        break;
    }
    case VRR_OPTION_TYPE_TEARDOWN: {
        VrrTearDown *TD = (VrrTearDown *)&Opt->Opt;
        int NumPId = RtlUlongByteSwap(TD->NumGlobalPathId);
        int i;

        Field = (InternalOption **) &SRP->VrrTearDown;
        for (i = 0; i < NumPId; i++) {
            VrrTrace(VA,3,"MQ:TD=2SRP",TD->Source,SRP->Token.NextVAddress,TD->PId[i].Address,
                     "Pid",RtlUlongByteSwap(TD->PId[i].PathId),"FrameSeqNo",SRP->FrameSeqNo);
            UpdatePacketIndex(VA, TD->PId[i].Address, RtlUlongByteSwap(TD->FrameSeqNo), TD->HopCount++,
                  SRP->Source, SRP->Dest, SRP->Token.LocIF, VRR_OPTION_TYPE_TEARDOWN);
        }
        break;
    }
    case VRR_OPTION_TYPE_SETUPREQ: {
        VrrSetupReq *SR = (VrrSetupReq *)&Opt->Opt;

        Field = (InternalOption **) &SRP->VrrSetupReq;
        VrrTrace(VA,3,"MQ:SR=2SRP",SR->Source,SRP->Token.NextVAddress,SR->Dest,
                 NULL,0,"FrameSeqNo",SRP->FrameSeqNo);
        UpdatePacketIndex(VA, SR->Source, RtlUlongByteSwap(SR->FrameSeqNo), SR->HopCount++,
                  SRP->Source, SRP->Dest, SRP->Token.LocIF, 
                  (SR->Type & VRR_SR_TYPE_REQUEST) ? VRR_OPTION_TYPE_SETUPREQ : VRR_OPTION_TYPE_SR_NACK);

        break;
    }
        
    default:
        VRRASSERT(!"MsgToSRP: bad message type");
        ExFreePool(Opt);
        return;
    }

    Opt->Next = *Field;
    *Field = Opt;
}

//* MsgMoveMultiToSRP
//
//  Move messages from a list to an SRP bound for a known destination.
//
//  Returns a count of how many options were added
//  and updates the packet size.
//
//  Should be called with the piggy-back cache locked,
//  if PrevPO is &PCache->List.
//
static uint
MsgMoveMultiToSRP(
    PbackCache *PCache,
    PbackOption **PrevPO,       // Pointer to list of options.
    SRPacket *SRP,
    uint *Size,                 // Packet size.
    const VirtualAddress Dest)  // May be NULL, meaning all destinations.
{
    PbackOption *PO;
    uint Count = 0;
    MiniportAdapter *VA;
    

    //
    // Get address for the VA struct of which the PCache arg is a member.
    //
    VA = CONTAINING_RECORD(PCache,MiniportAdapter,PCache);
    
    //
    // Iterate over all waiting options looking
    // for options for this destination.
    //
    while ((PO = *PrevPO) != NULL) {

        //
        // Should this message be sent in this SRPacket?
        // Yes, if the SRPacket has same NextHop as PO->Dest and if size permits.
        //
        if (VirtualAddressEqual(SRP->Token.NextVAddress, PO->Token.NextVAddress) &&