setup.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.
//

#include "headers.h"


//* SetupTransactAbort
//
// Helper for ReceiveSetup.
// Send a Teardown if we abort an optimistic lightweight transaction.
//
// Caller must not hold RT->Lock.
// Caller must not hold PCache->Lock.
//
void
SetupTransactAbort(
    MiniportAdapter *VA,
    VirtualAddress EndpointA,
    uint PathId,
    VirtualAddress Sender)
{
    RouteTableEntry *RTE;
    InternalVrrTearDown *TDOSender;
    InternalVrrTearDown *TDONextA = NULL;
    InternalVrrTearDown *TDONextB = NULL;
    VirtualAddress NextA;
    VirtualAddress NextB;

    VrrGlobalPathId PId;
    RTEFlags Flags;
    KIRQL OldIrql;
    
    RtlCopyMemory(&PId.Address, EndpointA, sizeof(VirtualAddress));
    PId.PathId = RtlUlongByteSwap(PathId);

    //
    // Create a TearDown cache entry for the rejected Setup.
    //
    KeAcquireSpinLock(&VA->TDC.Lock, &OldIrql);
    FindOrCreateTDCE(&VA->TDC,
                     EndpointA, 
                     PathId,
                     Sender);
    KeReleaseSpinLock(&VA->TDC.Lock, OldIrql);

    //
    // Send TearDown to NextA and NextB if we have an RTE for
    // the supplied EndpointA and PathId.
    //
    Flags.Flags = 0;
    Flags.VSet = 1;
    KeAcquireSpinLock(&VA->RT.Lock, &OldIrql);
    RTE = FindRTE(VA,
                  EndpointA,                //const VirtualAddress EndpointA,
                  VRR_ADDRESS_UNSPECIFIED,  //const VirtualAddress EndpointB,
                  PathId,                   //PathId,
                  VRR_ADDRESS_UNSPECIFIED,  //const VirtualAddress NextA,
                  VRR_IFID_UNSPECIFIED,     //VRRIf LocIFa,
                  VRR_IFID_UNSPECIFIED,     //VRRIf RemIFa,
                  VRR_ADDRESS_UNSPECIFIED,  //const VirtualAddress NextB,
                  VRR_IFID_UNSPECIFIED,     //VRRIf LocIFb,
                  VRR_IFID_UNSPECIFIED,     //VRRIf RemIFb,
                  Flags);
    if (RTE != NULL) {
        RTE->State = VRR_RTE_STATE_RETIRED;
        RTE->Timeout = RTERetireTimeout(RTE->Flags);
        if (RTE->A.Next != NULL) {
            RtlCopyMemory(NextA,RTE->A.Next->VAddress,sizeof(VirtualAddress));
            TDONextA=CreateTearDownOpt(VA, NextA, 1, sizeof(PId), &PId, TRUE, FALSE);
        }
        if (RTE->B.Next != NULL) {
            RtlCopyMemory(NextB,RTE->B.Next->VAddress,sizeof(VirtualAddress));
            TDONextB=CreateTearDownOpt(VA, NextB, 1, sizeof(PId), &PId, TRUE, FALSE);
        }
    }
    KeReleaseSpinLock(&VA->RT.Lock, OldIrql);

    //
    // Send TearDowns via Pback queue.
    //
    TDOSender=CreateTearDownOpt(VA, Sender, 1, sizeof(PId), &PId, TRUE, FALSE);
    MsgQueueMessage(VA, Sender, (InternalOption *) TDOSender, VRR_IFID_UNSPECIFIED,VRR_IFID_UNSPECIFIED,TDOWN_DELAY,NULL);
    VrrKdPrint("SetupTransactAbort: send Teardown(A=s) to d",EndpointA,Sender);

    if (TDONextA != NULL) {
        MsgQueueMessage(VA, NextA, (InternalOption *) TDONextA, VRR_IFID_UNSPECIFIED,VRR_IFID_UNSPECIFIED,TDOWN_DELAY,NULL);
        VrrKdPrint("SetupTransactAbort: send Teardown(A=s) to d",EndpointA,NextA);
    }

    if (TDONextB!= NULL) {
        MsgQueueMessage(VA, NextB, (InternalOption *) TDONextB, VRR_IFID_UNSPECIFIED,VRR_IFID_UNSPECIFIED,TDOWN_DELAY,NULL);
        VrrKdPrint("SetupTransactAbort: send Teardown(A=s) to d",EndpointA,NextB);
    }

}

//* ReceiveSetup
//
//  Receive a VRR Setup message. Called from ReceiveSRPacket.
//
//  Note: basic packet parsing performed in ReceiveSRPacket, which
//  provides us the VrrSetup structure in an SRPacket option.
//
void
ReceiveSetup(
    MiniportAdapter *VA,
    ProtocolAdapter *PA,
    InternalVrrSetup *InternalSetup,
    SRPacket *srp)
{
    KIRQL OldIrql;
    VirtualAddress *PVSET = NULL;
    VirtualAddress *MsgVSet = NULL;
    uint i;
    uint VSetLen;
    uint CountVSet;
    NodeTableEntry *NTE;
    uint PathId;
    VrrSetup *Setup;
    RouteTableEntry *RTE;
    TxToken TokA;
    TxToken TokB;
    FindNextHopResult Result;
    uint TransactAbort = FALSE;
    TearDownCacheEntry *TDC = NULL;
    RTEFlags Flags;
    uint DropSetup = FALSE;
    uint LoopTearDown = FALSE;
    uint Forwarding;
    uint LastHop = FALSE;
    uint TransactionAbort = FALSE;
    NeighborCacheEntry *NCE;
    uchar SnapNCEState = 0;
    uint FrameSeqNo;

#if DBG
    RtlZeroMemory(&TokA,sizeof(TxToken));
#endif
    RtlZeroMemory(&TokB,sizeof(TxToken));

    //
    // Find start of vset in VrrSetup message, and cardinality of vset.
    //    
    VRRASSERT(InternalSetup != NULL);
    Setup = &InternalSetup->Opt;
    PathId = RtlUlongByteSwap(Setup->PathId);
    FrameSeqNo = RtlUlongByteSwap(Setup->FrameSeqNo);
    MsgVSet = Setup->vset;
    VSetLen = (uint)InternalSetup->Opt.OptDataLen
             - sizeof(Setup->Source)
             - sizeof(Setup->Dest)
             - sizeof(Setup->Proxy)
             - sizeof(Setup->Flags)
             - sizeof(Setup->FrameSeqNo)
             - sizeof(Setup->HopCount)
             - sizeof(Setup->A)
             - sizeof(Setup->B)
             - sizeof(Setup->PathId)
             - sizeof(Setup->LocIF)
             - sizeof(Setup->RemIF)
             - sizeof(Setup->Prev)
             - sizeof(Setup->SRTarget);
    CountVSet = VSetLen / sizeof(VirtualAddress);
    
    //
    // Validate the VrrSetup message.
    //
    VrrKdPrint("RcvSetup", Setup->A, Setup->B);
    UpdatePacketIndex(VA, Setup->A, FrameSeqNo, Setup->HopCount,
                  Setup->Source, Setup->Dest, (VRRIf)PA->Index, VRR_OPTION_TYPE_SETUP);
    
    //
    // Ignore any Setup that we sent ourselves during a join attempt.
    // gregos: will need to strengthen this for DAD handling.
    //
    if (VirtualAddressEqual(VA->Address, Setup->Dest))
    if (VirtualAddressEqual(VA->Address, Setup->Source)) {
        VrrTrace(VA,2,"SR:SR=ignore Setup(s=self,d=self) (ToDo: DAD)",Setup->Source,Setup->A,Setup->B,NULL,0,NULL,0);
        goto ReleaseAndReturn;
    }

    //
    // Validate the Vset size.
    //
    if (VSetLen != CountVSet * sizeof(VirtualAddress)) {
        VrrTrace(VA,2,"SU:SU=Drop(BadVSetLen)",Setup->Source,NULL,Setup->Dest,
                   NULL,0, "SeqNo",FrameSeqNo);
        goto ReleaseAndReturn;
    }

    if (CountVSet == 0) {
        VrrTrace(VA,2,"SU:SU=Drop(CountVSet==0)",Setup->Source,NULL,Setup->Dest,
                   NULL,0, "SeqNo",FrameSeqNo);
        goto ReleaseAndReturn;
    }


    //
    // Ignore any Setup for which (Address,PathId) pair appears in
    // our TearDown cache. This can happen when a Setup and TearDown
    // are sent in quick succession and the TearDown overtakes the 
    // Setup while both are still in flight.
    //
    KeAcquireSpinLock(&VA->TDC.Lock, &OldIrql);
    TDC = FindTDCE(&VA->TDC, Setup->A, PathId, VRR_ADDRESS_UNSPECIFIED);
    KeReleaseSpinLock(&VA->TDC.Lock, OldIrql);
    if (TDC) {
        VrrTrace(VA,2,"SU:SU=Drop(inTDCache)",Setup->A,Setup->Source,Setup->B,"Pid",PathId,NULL,0);
        goto ReleaseAndReturn;
    }
    
    //
    // Handle Setup(A,PiD) that already exists in our Route Table.
    //
    KeAcquireSpinLock(&VA->RT.Lock, &OldIrql);
    Flags.Flags = 0;
    Flags.VSet = 1;
    RTE = FindRTE(VA,
                  Setup->A,                 //const VirtualAddress EndpointA,
                  VRR_ADDRESS_UNSPECIFIED,  //const VirtualAddress EndpointB,
                  PathId,                   //PathId,
                  Setup->Source,            //const VirtualAddress NextA,
                  VRR_IFID_UNSPECIFIED,     //VRRIf LocIFa,
                  VRR_IFID_UNSPECIFIED,     //VRRIf RemIFa,
                  VRR_ADDRESS_UNSPECIFIED,  //const VirtualAddress NextB,
                  VRR_IFID_UNSPECIFIED,     //VRRIf LocIFb,
                  VRR_IFID_UNSPECIFIED,     //VRRIf RemIFb,
                  Flags);
    if (RTE != NULL) {
        //
        // We already know about this (A,PathId) and we agree on NextA.
        // Drop this Setup message.
        //
        DropSetup = TRUE;
        VrrTrace(VA,1,"SU:SU=Drop(KnownNextA)",Setup->Source,Setup->A,Setup->B,"Pid",PathId,NULL,0);
    }
    else {
        RTE = FindRTE(VA,
                      Setup->A,                 //const VirtualAddress EndpointA,
                      VRR_ADDRESS_UNSPECIFIED,  //const VirtualAddress EndpointB,
                      PathId,                   //PathId,
                      VRR_ADDRESS_UNSPECIFIED,  //const VirtualAddress NextA,
                      VRR_IFID_UNSPECIFIED,     //VRRIf LocIFa,
                      VRR_IFID_UNSPECIFIED,     //VRRIf RemIFa,
                      VRR_ADDRESS_UNSPECIFIED,  //const VirtualAddress NextB,
                      VRR_IFID_UNSPECIFIED,     //VRRIf LocIFb,
                      VRR_IFID_UNSPECIFIED,     //VRRIf RemIFb,
                      Flags);
        if (RTE != NULL) {
            //
            // We already know about this (A,PathId) but we disagree on NextA.
            // This can happen if a Setup message gets looped back to us after
            // we have already forwarded it. The loop needs to be torn down.
            //
            LoopTearDown = TRUE;
        }
    }
    KeReleaseSpinLock(&VA->RT.Lock, OldIrql);
    if (DropSetup == TRUE)
        goto ReleaseAndReturn;
    if (LoopTearDown == TRUE) {
        VrrTrace(VA,1,"SU:SU=TxnAbort(A=d,PId) - disagree NextA",Setup->Source,Setup->A,Setup->B,NULL,0,NULL,0);

        TransactionAbort = TRUE;
        goto ReleaseAndReturn;
    }

    //
    // Apply consistency checks before proceeding.
    // The VRR paper describes this as "Optimistic Lightweight Transactions".
    //
    
    //
    // Optimistic Lightweight Transaction Stage 1.
    // ref "ignore setup messages ... from nodes that are not linked"
    // Conviently implemented elsewhere, search for:
    //         Optimistic Lightweight Transaction Stage 1 
    //

    //
    // Optimistic Lightweight Transaction Stage 2.
    // ref "(endpointA == node.nodeid && sender != node.nodeid)) "
    //
    if (VirtualAddressEqual(Setup->A, VA->Address) &&
        ! VirtualAddressEqual(srp->Source,VA->Address)) {

        VrrTrace(VA,1,"SR:SR=OLT(4)=FAIL: OLT(2)=FAIL",Setup->Source,Setup->A,Setup->B,NULL,0,NULL,0);
        TransactionAbort = TRUE;
        goto ReleaseAndReturn;
    }

    //
    // Optimistic Lightweight Transaction Stage 3.
    // ref "forward setup on", see below.
    //
    
    //
    // Optimistic Lightweight Transaction Stage 4.
    // ref "did not add endpointA to my vset"
    // Note, at this point we do not disturb our vset.
    //
    if (VirtualAddressEqual(Setup->B, VA->Address) &&
        IsCandidateNeighbor(VA,Setup->A,CountVSet,Setup->vset) == FALSE) {
        VrrTrace(VA,1,"SR:SR=OLT(4)=FAIL: did not add endpointA to my vset",Setup->Source,Setup->A,Setup->B,NULL,0,NULL,0);
        TransactionAbort = TRUE;
        goto ReleaseAndReturn;
    }

    //
    // Optimistic Lightweight Transaction Stage 5.
    // ref "message was delivered to the wrong node, teardown path", see below.
    //

    //
    // Optimistic Lightweight Transaction Stage 6.
    // Issue TearDown if we already have an RTE with same (A,B,PathId).
    // ref "tear down path because there is a loop".
    //
    KeAcquireSpinLock(&VA->RT.Lock, &OldIrql);
    RTE = FindRTE(VA, Setup->A, Setup->B, PathId,
                  VRR_ADDRESS_UNSPECIFIED, VRR_IFID_UNSPECIFIED, VRR_IFID_UNSPECIFIED,
                  VRR_ADDRESS_UNSPECIFIED, VRR_IFID_UNSPECIFIED, VRR_IFID_UNSPECIFIED,
                  Flags);
    KeReleaseSpinLock(&VA->RT.Lock, OldIrql);

    if (RTE != NULL) {
        VrrTrace(VA,1,"SU:SU=OLT(6)=FAIL: tear down path because there is a loop",Setup->Source,Setup->A,Setup->B,NULL,0,NULL,0);

        TransactionAbort = TRUE;
        goto ReleaseAndReturn;
    }

    //
    // Done with Optimistic Lightweight Transaction handling, for now.
    //
    
    //
    // There is a possible race between the hello protocol and a run
    // of (SetupReq, Setup) in which our link to the node forwarding
    // the setup may have undergone repair but the repair has not yet
    // been signalled by hello. Deal with this by pre-empting hello.
    //
    KeAcquireSpinLock(&VA->NC.Lock, &OldIrql);
    NCE = FindNCE(&VA->NC,
                  Setup->Source,
                  Setup->RemIF,          // His LocIF, my RemIF.
                  Setup->LocIF,          // His RemIF, my LocIF.
                  VRR_NCE_STATE_ANY);

    if (NULL != NCE) {
        if (NCE->State == VRR_NCE_STATE_PENDING) {
            NCE->State = VRR_NCE_STATE_LINKED;
        }
        SnapNCEState = NCE->State;
    }    

    KeReleaseSpinLock(&VA->NC.Lock, OldIrql);
    
    if (! (SnapNCEState & VRR_NCE_STATE_LINKED)) {
        VrrTrace(VA,1,"SU:SU=aborted: NCE(s)!=LINKED",Setup->Source,Setup->A,Setup->B,NULL,0,NULL,0);
        TransactionAbort = TRUE;
        goto ReleaseAndReturn;
    }

    //
    // Find NextHop(A). This is the node that sent us the Setup.
    //
    // Note: use GetPhysnTok() to avoid race with hello 
    // during boot, when FNH() would need to be preceded
    // by hello=ACTIVE from the Setup->Source.
    //
    if (!GetPhysNeighborTxToken(VA,Setup->Source,Setup->RemIF,Setup->LocIF,&TokA,VRR_NCE_STATE_LINKED)) {
        //
        // Cannot resolve NextHop(A). Abort.
        //
        VrrTrace(VA,1,"SU:SU=join fail: cannot resolve NextHop(s=A)",Setup->Source,Setup->A,Setup->B,NULL,0,NULL,0);
        TransactionAbort = TRUE;
        goto ReleaseAndReturn;
    }
    
    //
    // Find NextHop(dest), where dest is proxy or EndpointB.
    //
    Forwarding = TRUE;
    if (VRR_MSG_FLAG_PASTPROXY & Setup->Flags) {
        //
        // A setup that is past its proxy should arrive
        // at the joining node in one hop. If it arrived 
        // with us and is not addressed to us then it has
        // been misrouted.
        //
        if (VirtualAddressEqual(VA->NT.Self->Address, Setup->Dest) ||