route.c

Vitual Ring Routing 管你知不知道

    // Salvage messages and (MB) packets.
    //
    SalvagePacketsFromMaintBuf(VA, NCE->VAddress,
                               NCE->LocIF, NCE->RemIF);

    //
    // Purge message queue of messages for this destination.
    //
    MsgFailLink(VA, NCE->VAddress, NCE->LocIF, NCE->RemIF);

    //
    // Safe to release memory.
    //
    ReleaseNCE(NCE);
    IoFreeWorkItem(Item);
    ExFreePool(RDDC);
}


//* RouteFailLink
//
//  Helper for failing a link associated with an NCE.
//
//  Caller must hold NC->Lock and therefore cannot take
//  RT->Lock to perform the downdate inline. Hence we 
//  queue an IoWorkQueueItem to do the work.
//
void
RouteFailLink(
    MiniportAdapter *VA,
    NeighborCacheEntry *NCE)
{
    PIO_WORKITEM Item;
    RouteFailLinkContext *RDDC;

    VRRASSERT(NCE != NULL);
    
    RDDC = ExAllocatePool(NonPagedPool, sizeof *RDDC);
    if (RDDC == NULL)
        return;
    
    Item = IoAllocateWorkItem(VA->DeviceObject);
    if (Item == NULL) {
        ExFreePool(RDDC);
        return;
    }
    
    //
    // Keep a ref on NCE so that locks can be released. The worker will
    // release the ref when done.
    //
    AddRefNCE(NCE);
    RDDC->NCE = NCE;
    RDDC->VA = VA;
    RDDC->Item = Item;
    IoQueueWorkItem(Item, RouteFailLinkWorker, DelayedWorkQueue, RDDC);
}

//* DistDirectLeftSR
//
// Helper for FindNextHop when directing SR around perimeter of ring.
// Given (ay,ax) returns Uint64DistanceLeft(ax,ay).
//
static unsigned __int64
DistDirectLeftSR(
    unsigned __int64 ay,
    unsigned __int64 ax)
{
    return Uint64DistanceLeft(ax,ay);
}

//* DistDirectRightSR
//
// Helper for FindNextHop when directing SR around perimeter of ring.
// Given (ay,ax) returns Uint64DistanceRight(ax,ay).
//
static unsigned __int64
DistDirectRightSR(
    unsigned __int64 ay,
    unsigned __int64 ax)
{
    return Uint64DistanceRight(ax,ay);
}

//* IsValidNextHop
//
//  Helper for FindNextHop.
//
//  Returns TRUE iff NCE for supplied Endpoint is valid for use.
//
static uint
IsValidNextHop(
    unsigned __int64 Dest,
    RouteTableEndpoint *EP,
    RTEFlags Flags)
{
    uint Result = FALSE;

    if (EP->Next==NULL)
        //
        // Common case: EP refers to self.
        //
        Result = TRUE;
    else if (EP->Next->State==VRR_NCE_STATE_ACTIVE)
        //
        // Common case: NextHop is on active link.
        //
        Result = TRUE;
    else if (EP->uint64Address==Dest && Flags.Hops1 == 1 &&
             (EP->Next->State & VRR_NCE_STATE_LINKED) != 0)
        //
        // Deliver via NCE(LINKED) if NCE==Dest.
        //
        Result = TRUE;
    else if (Flags.VSet == 1 &&
             (EP->Next->State & VRR_NCE_STATE_LINKED) != 0)
        //
        // Use VSet routes via NCE that is only LINKED.
        // Important when NCE is a major bridge - it may
        // know many usable routes even if missing some
        // VSet routes of its own.
        //
        Result = TRUE;
    else
        Result = FALSE;

    return Result;
}

//* RankEndpoint
//
// Helper for FindNextHop. Defines preference between endpoints.
//
static uint
RankEndpoint(
    MiniportAdapter *VA,
    RouteTableEndpoint *EP,
    RTEFlags Flags)
{
    if (VirtualAddressEqual(EP->Address,VA->Address))
        return 5;
    else if (Flags.Hops1 == 1)
        return 4;
    else if (Flags.Hops2 == 1)
        return 3;
    else if (Flags.Zero == 1)
        return 2;
    else
        return 1;
}

//* FindNextHop  // FNH:
//
//  Selects next hop towards destination by inspecting Route Table.
//
//  Updates the callers TxToken with sufficient state for
//  the packet be transmitted without further reference to 
//  the Route Table.
//
//  Note the special-case support for routing SetupReq when the 
//  virtual ring is being initialized or somehow inconsistent. In
//  particular the SRcAntiRoute and SRFlags arguments are used when
//  routing to a target destination is failing.
//
//  Returns:
//    SuccessFwd iff the next hop is elsewhere
//    SuccessRcvSelf iff self exactly matches self
//    SuccessRcvNearest iff self is closest match to destination
//    Error: internal error occurred.
//
//  Caller must not hold the RT->Lock.
//  Caller must not hold the NC->Lock.
//  Caller must not hold the VA->Lock.
//
FindNextHopResult
FindNextHop(
    MiniportAdapter *VA,
    VirtualAddress Dest,
    VRRIf LocIF,
    VRRIf RemIF,
    TxToken *Tok,
    AddressList *SRcAntiRoute,
    uchar SRFlags)
{
    KIRQL OldIrql;
    RouteTable *RT = &VA->RT;
    RouteTableEntry *RTE;
    RouteTableEntry *BestRTE;
    RouteTableEndpoint *BestEndpoint = NULL;
    unsigned __int64 uint64Dest = VirtualAddressToUint64(Dest);
    pFuncUi64Distance *pDistanceFunc = Uint64VirtualAddressDistance;
    
    FindNextHopResult Result = Error;

    //
    // If this is an attempt to route to self then we are done.
    //
    if (VirtualAddressEqual(VA->Address,Dest)) {
        return SuccessRcvSelf;
    }

    //
    // There will be no routing state if we are the boot node.
    // In that case we receive everything in order that other
    // nodes may join the ring.
    //
    if (RT->FirstRTE == SentinelRTE(RT)) {
        VrrKdPrint("FNH(d): no RT state - return SuccessRcvNearest (boot node?)",NULL,Dest);
        return SuccessRcvNearest;
    }

    //
    // Special case for SetupReq.
    //
    // Force a SetupReq around the perimeter of the virtual ring in
    // a direction specified by the SRFlags argument. 
    //
    if (SRFlags == VRR_SR_DIRECT_LHS) {
        InterlockedIncrement(&VA->CountFNHsendSRleft);
        VrrTrace(VA,3,"RT:**=FNH_(SendSRleft)",VA->Address,NULL,Dest,NULL,0,NULL,0);
        pDistanceFunc = DistDirectLeftSR;
    }
    else if (SRFlags == VRR_SR_DIRECT_RHS) {
        InterlockedIncrement(&VA->CountFNHsendSRright);
        VrrTrace(VA,3,"RT:**=FNH_(SendSRright)",VA->Address,NULL,Dest,NULL,0,NULL,0);
        pDistanceFunc = DistDirectRightSR;
    }

    //
    // Search for the best endpoint given Dest.
    //
    KeAcquireSpinLock(&VA->RT.Lock, &OldIrql);
    KeAcquireSpinLockAtDpcLevel(&VA->NC.Lock);

    for (RTE = RT->FirstRTE; RTE != SentinelRTE(RT); RTE = RTE->Next) {
        RouteTableEndpoint *Endpoint;

        //
        // Consider only ACTIVE routes.
        //
        if (RTE->State != VRR_RTE_STATE_ACTIVE)
            continue;

        //
        // Consider both endpoints in the RTE.
        //
        Endpoint = NULL;
        while (Endpoint != &RTE->B) {
        
            Endpoint = (NULL == Endpoint) ? &RTE->A : &RTE->B;

            //
            // Consider only Endpoints on valid (usable) next hop links.
            //
            if (IsValidNextHop(uint64Dest,Endpoint,RTE->Flags) == FALSE)
                continue;

            //
            // SetupReq (SR) uses SRcAntiRoute to prevent an SR being
            // routed to a node that recently Nacked the SR.
            //
            if (AddressListContains(SRcAntiRoute,Endpoint->Address)) {
                InterlockedIncrement(&VA->CountFNHSRcAntiRoute);
                VrrTrace(VA,4,"RT:**=FNH_(SRcAntiRouteEP)",VA->Address,NULL,Endpoint->Address,NULL,0,NULL,0);
                continue;
            }

            //
            // If we are on the SR SRcAntiRoute then we must override the
            // standard logic for receiving if we have the closest known
            // address to the destination, so that the SR can progress
            // beyond us via the next nearest address that we known.
            //
            if (AddressListContains(SRcAntiRoute,VA->Address) &&
                Endpoint->Next == NULL) {
                InterlockedIncrement(&VA->CountFNHSRcAntiRoute);
                VrrTrace(VA,4,"RT:**=FNH_(SRcAntiRouteSelfNearest)",VA->Address,NULL,Dest,NULL,0,NULL,0);
                continue;
            }

            //
            // Endpoint must satisfy our caller's IF arguments,
            //
            if (LocIF != VRR_IFID_UNSPECIFIED && 
                Endpoint->Next != NULL &&
                LocIF != Endpoint->Next->LocIF)
                continue;
            if (RemIF != VRR_IFID_UNSPECIFIED && 
                Endpoint->Next != NULL &&
                RemIF != Endpoint->Next->RemIF)
                continue;

            //
            // Ignore routes created by the partition repair protocol unless
            // they exactly match the intended destination.
            //
            if (RTE->Flags.Zero == 1 &&
                ! VirtualAddressEqual(Endpoint->Address, Dest))
                continue;

            //
            // Endpoint is on an active route via acceptable interface(s).
            // At the outset it makes a reasonable starting point for search.
            //
            if (BestEndpoint == NULL) {
                BestEndpoint = Endpoint;
                BestRTE = RTE;
                continue;
            }
            
            //
            // We want the closest endpoint(s) to Dest.
            // Endpoint address must be at least as close to dest as
            // BestEndpoint.
            //
            if ((*pDistanceFunc)(Endpoint->uint64Address, uint64Dest) >
                (*pDistanceFunc)(BestEndpoint->uint64Address, uint64Dest))
                continue;

            //
            // Endpoint may beat BestEndpoint on name distance.  
            //
            if ((*pDistanceFunc)(Endpoint->uint64Address, uint64Dest) <
                (*pDistanceFunc)(BestEndpoint->uint64Address, uint64Dest)) {
                
                BestEndpoint = Endpoint;
                BestRTE = RTE;
                continue;
            }

            //
            // Endpoint and BestEndpoint are same name distance from Dest.
            //
            VRRASSERT((*pDistanceFunc)(Endpoint->uint64Address, uint64Dest) == 
                      (*pDistanceFunc)(BestEndpoint->uint64Address, uint64Dest));

            //
            // Given two equidistant endpoints, choose the one closest
            // to our right hand side.
            //
            if (IsCloserRight(BestEndpoint->Address , Endpoint->Address, Dest))
                continue;
            if (IsCloserRight(Endpoint->Address , BestEndpoint->Address, Dest)) {
                BestEndpoint = Endpoint;
                BestRTE = RTE;
                continue;
            }

            //
            // At this point it must be that Endpoint and BestEndpoint have the same address.
            //
            VRRASSERT(VirtualAddressEqual(Endpoint->Address, BestEndpoint->Address));

            //
            // The endpoint is fixed for the remainder of this iteration.
            // It remains to choose between alternate routes to endpoint.
            //
            // Route to Endpoint may beat route to BestEndpoint on rank.  
            //
            if (RankEndpoint(VA,Endpoint,RTE->Flags) < RankEndpoint(VA,BestEndpoint,BestRTE->Flags))
                continue;
            if (RankEndpoint(VA,Endpoint,RTE->Flags) > RankEndpoint(VA,BestEndpoint,BestRTE->Flags)) {
                BestEndpoint = Endpoint;
                BestRTE = RTE;
                continue;
            }
            
            //
            // The route to Endpoint and the route to BestEndpoint have equal rank.
            //
            VRRASSERT(RankEndpoint(VA,Endpoint,RTE->Flags) == 
                      RankEndpoint(VA,BestEndpoint,BestRTE->Flags));
            
            //
            // For Hops1 and Hops2 prefer route with lowest ETT.
            //
            if (RTE->Flags.Hops1 == 1 || RTE->Flags.Hops2 == 1)
            if (RTE->ETT < BestRTE->ETT) {
                BestEndpoint = Endpoint;
                BestRTE = RTE;
                continue;
            }
            
            //
            // Prefer the route with the higher value of PathId.
            //
            if (RTE->PathId > BestRTE->PathId) {
                BestEndpoint = Endpoint;
                BestRTE = RTE;
                continue;
            }
        }
    }
    
    //
    // Finished searching route table.
    //
    if (NULL == BestEndpoint) {
        //
        // Unable to determine route.
        //
        Result = Error;
        
    }
    else if (NULL == BestEndpoint->Next) {
        //
        // Having a null next hop means we are receiving locally.
        //
        VRRASSERT(VirtualAddressEqual(VA->Address,BestEndpoint->Address));
        if (VirtualAddressEqual(VA->Address,Dest))
            Result = SuccessRcvSelf;
        else
            Result = SuccessRcvNearest;

    }
    else {
        //
        // We are forwarding.
        //
        ProtocolAdapter *PA;
        Result = SuccessFwd;
        
        PA=FindPhysicalAdapterFromIndex(VA, BestEndpoint->Next->LocIF);
        
        if (NULL == PA) {
            //
            // Error. We are forwarding but cannot get the Protocol Adapter address.
            //
            KdPrint(("FNH: error in FindPhysicalAdapterFromIndex(%u)\n",BestEndpoint->Next->LocIF));
            Result = Error;
            
        }
        else if (NULL != Tok) {
            //
            // Initialize the caller's TxToken.
            //
            NeighborCacheEntry *NCE = BestEndpoint->Next;

            RtlZeroMemory(Tok, sizeof(TxToken));
            RtlCopyMemory(Tok->Source, VA->Address, sizeof(VirtualAddress));
            RtlCopyMemory(Tok->Dest, Dest, sizeof(VirtualAddress));
            RtlCopyMemory(Tok->NextVAddress, NCE->VAddress, sizeof(VirtualAddress));
            RtlCopyMemory(Tok->NextPAddress, NCE->PAddress, sizeof(PhysicalAddress));
            Tok->LocIF = NCE->LocIF;
            Tok->RemIF = NCE->RemIF;
            Tok->PA = PA;
        }
    }

    KeReleaseSpinLockFromDpcLevel(&VA->NC.Lock);
    KeReleaseSpinLock(&VA->RT.Lock, OldIrql);

    return Result;
}

//* FindVSetRoute
//
//  Returns RTE(A,B) or RTE(B,A) if one exist, else returns NULL.
//
//  Caller must hold RT->Lock.
//
RouteTableEntry *
FindVSetRoute(
    MiniportAdapter *VA,
    const VirtualAddress EndpointA,
    const VirtualAddress EndpointB)
{
    RouteTableEntry *RTE;
    RTEFlags Flags;

    Flags.Flags = 0;
    Flags.VSet = 1;
    RTE = FindRTE(VA, EndpointA, EndpointB, VRR_PATHID_UNSPECIFIED, // (A,B,PathId).
                       VRR_ADDRESS_UNSPECIFIED, VRR_IFID_UNSPECIFIED, VRR_IFID_UNSPECIFIED, // NextA.
                       VRR_ADDRESS_UNSPECIFIED, VRR_IFID_UNSPECIFIED, VRR_IFID_UNSPECIFIED, // NextB.
                       Flags);
    if (RTE == NULL)
        RTE = FindRTE(VA, EndpointB, EndpointA, VRR_PATHID_UNSPECIFIED, // (B,A,PathId).
                           VRR_ADDRESS_UNSPECIFIED, VRR_IFID_UNSPECIFIED, VRR_IFID_UNSPECIFIED, // NextA.
                           VRR_ADDRESS_UNSPECIFIED, VRR_IFID_UNSPECIFIED, VRR_IFID_UNSPECIFIED, // NextB.
                           Flags);

    return RTE;

}

//* IsNullTxToken
//
//  Returns TRUE iff given TxToken is all zeros.
//
boolint
IsNullTxToken(TxToken *Token)
{
    TxToken NullToken;
    RtlZeroMemory(&NullToken,sizeof(NullToken));

    return RtlEqualMemory(Token, &NullToken, sizeof(NullToken));
}