setupreq.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"

//* ForwardSR
//
//  Check if a SetupReq is for us. If not, try to
//  copy and forward it.
//
//  Originally a generic routine but in practice was
//  only used on the SR forwarding path.
//
//  Returns TRUE iff the option was forwarded.
//
boolint
ForwardSR(
    MiniportAdapter *VA,
    InternalOption *InternalOpt,
    AddressList *SRcAntiRoute)
{
    uint Forwarded = FALSE;
    VrrMsgPrefix *MsgOld = (VrrMsgPrefix *)&InternalOpt->Opt;
    FindNextHopResult Result;
    VrrSetupReq *SROld = (VrrSetupReq *)&InternalOpt->Opt;
    TxToken Token;
    uint AmProxy = FALSE;
    uint FrameSeqNo = RtlUlongByteSwap(SROld->FrameSeqNo);
    
    VRRASSERT(VRR_OPTION_TYPE_SETUPREQ == InternalOpt->Opt.optionType);
    VRRASSERT((SROld->Type & VRR_SR_TYPE_NACK) || AddressListCount(SRcAntiRoute) != 0);
    VRRASSERT((SROld->Type & VRR_SR_TYPE_NACK) || AddressListContains(SRcAntiRoute,SROld->Source));

    //
    // Ensure that forwarding will not exceed max hop count on this message.
    //
    if (MsgOld->HopCount >= VRR_MAX_HOPCOUNT) {
        VrrTrace(VA,2,"SR:SR=Drop(HopsXs)",SROld->Source,SROld->Source,SROld->Dest,NULL,0,"SeqNo",FrameSeqNo);
        InterlockedIncrement((PLONG)&VA->CountSRDropHopCount);
        return TRUE;
    }

    //
    // Check if we should perform proxy functions.
    //
    if (! (SROld->Flags & VRR_MSG_FLAG_PASTPROXY))
    if (VirtualAddressEqual(SROld->Dest,VA->Address)) {
        //
        // We are the proxy: swap the Dest and Proxy addresses.
        //
        VirtualAddress Swap;
        
        //
        // Adjust the message as though routed beyond proxy.
        //
        RtlCopyMemory(Swap, SROld->Dest, sizeof(VirtualAddress));
        RtlCopyMemory(SROld->Dest, SROld->Proxy, sizeof(VirtualAddress));
        RtlCopyMemory(SROld->Proxy, Swap, sizeof(VirtualAddress));
        SROld->Flags |= VRR_MSG_FLAG_PASTPROXY;
        AmProxy = TRUE;
    }

    //
    // Deal with the case of the last hop of an SR(NACK) to a node joining the ring.
    // The SR(NACK) is trying to reach the joiner's proxy, and the final hop uses
    // physical neighbour state because the mainline forwarding state may be incomplete.
    //
    if (AmProxy && (SROld->Type & VRR_SR_TYPE_NACK)) {
        InternalOption *NewOpt;
        VrrSetupReq *SRNew;

        //
        // Bail if the originator is no longer a linked neighbour of ours.
        //
        if (! GetPhysNeighborTxToken(VA,SROld->Dest,VRR_IFID_UNSPECIFIED,
                                     VRR_IFID_UNSPECIFIED,&Token,VRR_NCE_STATE_LINKED)) {
            VrrTrace(VA,2,"SR:SR=Drop(ProxyNoNCE)",VA->Address,NULL,SROld->Dest,NULL,0,"FrameSeqNo",FrameSeqNo);
            return TRUE;
        }

        if ((NewOpt=CopyInternalOption(VA,InternalOpt)) == NULL) {
            VrrKdPrint("FwdSR: error, NULL==CopyInternalOption()",NULL,NULL);
            return TRUE;        
        }
        SRNew = (VrrSetupReq *)&NewOpt->Opt;
        VrrTrace(VA, 2,"SR:SR=Fwd_(NACKJoinProxy)",SRNew->Source,Token.NextVAddress,SRNew->Dest,NULL,0,"FrameSeqNo",FrameSeqNo);
        MsgQueueMessage(VA, SRNew->Dest, NewOpt, VRR_IFID_UNSPECIFIED,VRR_IFID_UNSPECIFIED,FWD_DELAY,&Token);
        return TRUE;
    }

    //
    // Current routing state dictates how to handle the message. 
    //
    Result = FindNextHop(VA,
                         SROld->Dest,
                         VRR_IFID_UNSPECIFIED,
                         VRR_IFID_UNSPECIFIED,
                         &Token,
                         SRcAntiRoute,
                         SR_DIRECTION_BITS(SROld->Type));

    if (Result == Error) {
        VrrTrace(VA,2,"SR:SR=Drop(ErrFNH)",SROld->Source,NULL,SROld->Dest,NULL,0,"FrameSeqNo",FrameSeqNo);
        return TRUE;
    }

    if (Result == SuccessFwd) {
        //
        // We are not the destination or the closest node to it.
        // Copy and forward the message.
        //
        InternalOption *NewOpt = NULL;
        VrrSetupReq *SRNew;

        if ((NewOpt=CopyInternalOption(VA,InternalOpt)) == NULL) {
            VrrKdPrint("FwdSR: error, NULL==CopyInternalOption()",NULL,NULL);
            return TRUE;        
        }

        SRNew = (VrrSetupReq *)&NewOpt->Opt;
        if (SRNew->Flags & VRR_MSG_FLAG_JOIN_ATTEMPT)
            SRNew->Flags |= VRR_MSG_FLAG_JOIN_ATTEMPT;
        MsgQueueMessage(VA, SRNew->Dest, NewOpt, VRR_IFID_UNSPECIFIED,VRR_IFID_UNSPECIFIED,FWD_DELAY,&Token);
        return TRUE;
    }

    //
    // We are expected to receive this message.
    //
    return FALSE;

}

//* SendSRNack
//
// Reject the sender as a neighbor. Send msg SetupReq(NACK).
// Use the sender's FrameSeqNo to match original SR->FrameSeqNo.
//
void
SendSRNack(
    MiniportAdapter *VA,
    VirtualAddress SRSource,
    VirtualAddress SRProxy,
    uint FrameSeqNo,
    VirtualAddress SRTarget,
    uchar SRFlags)
{
    InternalVrrSetupReq *SRNack;

    SRNack = CreateSetupReqOpt(VA, 
                               SRSource,
                               VRR_SR_TYPE_NACK, 
                               SRProxy,
                               FrameSeqNo,
                               SRTarget,
                               NULL);
    
    if (SRNack == NULL)
        return;

    if (SRFlags & VRR_MSG_FLAG_JOIN_ATTEMPT)
        SRNack->Opt.Flags |= VRR_MSG_FLAG_JOIN_ATTEMPT;

    if (ForwardSR(VA,(InternalOption *)SRNack,NULL) != TRUE) {
        //
        // Failed to forward the Nack: drop it and protest.
        //
        VrrTrace(VA,2,"SR:SR=Drop(Fwd(SendNack)==F)",SRTarget,SRProxy,SRSource,NULL,0,"FrameSeqNo",FrameSeqNo);
    }

    VrrTrace(VA,3,"SR:SR=Rcv_(SendNack)",SRTarget,SRProxy,SRSource,NULL,0,"FrameSeqNo",FrameSeqNo);

    //
    // ForwardSR will have clone the SRNack iff put to MsgQ.
    //
    ExFreePool(SRNack);

}

//* ReceiveSetupReq
//
//  Receive a VRR SetupReq message. Called from ReceiveSRPacket.
//
//  Note: basic packet parsing performed in ReceiveSRPacket, which
//  provides us the VrrSetupReq structure in an SRPacket option.
//
void
ReceiveSetupReq(
    MiniportAdapter *VA,
    ProtocolAdapter *PA,
    InternalVrrSetupReq *InternalSetupReq,
    SRPacket *srp)
{
    KIRQL OldIrql;
    VirtualAddress *source;
    VirtualAddress *PVSET = NULL;
    VirtualAddress *MsgVSet = NULL;
    uint i;
    uint VSetLen;
    uint CountVSet;
    uint IsProxy = FALSE;
    VrrSetupReq *SetupReq;
    TxToken Token;
    FindNextHopResult Result;
    uint NewPXE;
    uint CountSRcAntiRoute;
    uint FrameSeqNo;
    AddressList *SRcAntiRoute = NULL;
    Time Now = KeQueryInterruptTime();
    InternalVrrSetup *Setup = NULL;
    uint SentSetup = FALSE;

    //
    // Find start of vset in VrrSetupReq message, and cardinality of vset.
    //
    VRRASSERT(InternalSetupReq != NULL);
    source = &InternalSetupReq->Opt.Source;
    SetupReq = &InternalSetupReq->Opt;
    FrameSeqNo = RtlUlongByteSwap(SetupReq->FrameSeqNo);
    CountSRcAntiRoute = SetupReq->CountSRcAntiRoute;
    MsgVSet = &SetupReq->addr[CountSRcAntiRoute];
    VSetLen = (uint)SetupReq->OptDataLen
             - sizeof(SetupReq->Type)
             - sizeof(SetupReq->Source)
             - sizeof(SetupReq->Dest)
             - sizeof(SetupReq->Proxy)
             - sizeof(SetupReq->Flags)
             - sizeof(SetupReq->FrameSeqNo)
             - sizeof(SetupReq->HopCount)
             - sizeof(SetupReq->Target)
             - sizeof(SetupReq->CountSRcAntiRoute)
             - (CountSRcAntiRoute * sizeof(VirtualAddress));
    CountVSet = VSetLen / sizeof(VirtualAddress);
    
    //
    // Validate the VrrSetupReq message.
    //
    VrrTrace(VA, 3, (SetupReq->Type & VRR_SR_TYPE_REQUEST) ? "SR:SR=Rcv_(Req)" : "SR:SR=Rcv_(Nack)",
        SetupReq->Source, SetupReq->Source, SetupReq->Dest, "CountSRcAntiRoute", CountSRcAntiRoute, "FrameSeqNo" , FrameSeqNo);
    if (CountSRcAntiRoute != 0) {
        VrrTrace(VA,3,"SR:SR=Rcv_(NonZBL)",SetupReq->Source,SetupReq->Source,SetupReq->Dest,
               "CountSRcAntiRoute", CountSRcAntiRoute,"FrameSeqNo" , FrameSeqNo);
    }
    if (CountSRcAntiRoute > (uint)InterlockedCompareExchange((PLONG)&VA->MaxPLESRcAntiRouteRcv,0,0))
        VA->MaxPLESRcAntiRouteRcv = CountSRcAntiRoute;

    if (VSetLen != CountVSet * sizeof(VirtualAddress)) {
        VrrTrace(VA,2,"SR:SR=Drop(BadVsetLen)",SetupReq->Source,SetupReq->Source,SetupReq->Dest,
                   "CountSRcAntiRoute",CountSRcAntiRoute, "SeqNo",FrameSeqNo);
        return;
    }

    if (CountVSet == 0) {
        VrrTrace(VA,2,"SR:SR=Drop(CountVSet==0)",SetupReq->Source,SetupReq->Source,SetupReq->Dest,
                   "CountSRcAntiRoute",CountSRcAntiRoute, "SeqNo",FrameSeqNo);
        return;
    }
    
    if ((SetupReq->Type & VRR_SR_TYPE_NACK)==0 &&
        (SetupReq->Type & VRR_SR_TYPE_REQUEST)==0 ) {
            VrrTrace(VA,2,"SR:SR=Drop(BadType)",SetupReq->Source,SetupReq->Source,SetupReq->Dest,
                   "Type",SetupReq->Type, "SeqNo",FrameSeqNo);
        return;
    }
    
    //
    // Add to packet index and check for looping messages.
    // The only time we should see a dup (FrameSeqNo,Type) is on SR(NACK).
    //
    NewPXE = UpdatePacketIndex(VA, SetupReq->Source, FrameSeqNo, SetupReq->HopCount,
                               SetupReq->Source, SetupReq->Dest, (VRRIf)PA->Index,
                               (SetupReq->Type & VRR_SR_TYPE_REQUEST) ? VRR_OPTION_TYPE_SETUPREQ : VRR_OPTION_TYPE_SR_NACK);
    if (NewPXE == FALSE &&
        (SetupReq->Type & VRR_SR_TYPE_NACK)==0) {
            VrrTrace(VA,2,"SR:SR=Drop(Dup)",SetupReq->Source,SetupReq->Source,SetupReq->Dest,NULL,0,"SeqNo",FrameSeqNo);
        InterlockedIncrement((PLONG)&VA->CountSRDropLoop);
        return;
    }

    //
    // Ignore any SetupReq that we sent ourselves while attempting join.
    // gregos: will need to strengthen this for DAD handling.
    //
    if (VirtualAddressEqual(VA->Address, SetupReq->Dest))
    if (VirtualAddressEqual(VA->Address, SetupReq->Source)) {
        VrrTrace(VA,2,"SR:SR=Drop(BadSelf)",SetupReq->Source,SetupReq->Source,SetupReq->Dest,NULL,0,"SeqNo",FrameSeqNo);
        return;
    }

    //
    // Construct SRcAntiRoute of addresses the orginator has asked us
    // to avoid for purposes of forwarding this SR. Reason is that
    // SetupRequests (SR) may get captured in a region of the mesh
    // that has local knowledge of addresses numerically close to
    // the destination address with no through routes allowing SR
    // to escape the region. The numerically close nodes will Nack
    // the SR and subsequent SR's use SRcAntiRoute to avoid ending up
    // at a node that has already Nacked the SR. This is most likely
    // to occur during initialization or after large-scale failure.
    //
    SRcAntiRoute = AddressListFromArray(&SetupReq->addr[0],CountSRcAntiRoute);

    //
    // In addition to the senders SRcAntiRoute, which may be NULL, we
    // always exclude the SR->Source from our forwarding decisions.
    //
    SRcAntiRoute = AddressListAdd(SRcAntiRoute,SetupReq->Source);

    //
    // Likewise ignore SetupReq that we sent ourselves and we are now 
    // nearest to Dest; this can happen when we attempt vset repair
    // and our SetupReq gets returned to us.
    // gregos: will need to strengthen this for DAD handling.
    //
    if (VirtualAddressEqual(VA->Address, SetupReq->Source)) {

        Result = FindNextHop(VA,
                             SetupReq->Dest,
                             VRR_IFID_UNSPECIFIED,
                             VRR_IFID_UNSPECIFIED,
                             NULL,
                             SRcAntiRoute,
                             NULL_SR_FLAGS);
                             
        if (Result == SuccessRcvNearest) {
            VrrTrace(VA,2,"SR:SR=Drop(BadSelf2)",SetupReq->Source,SetupReq->Source,SetupReq->Dest,NULL,0,"SeqNo",FrameSeqNo);
            InterlockedIncrement((PLONG)&VA->CountMisroutedSetupReq);