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

#define VRR_MIN_RTE_REFCNT    2     // RefCnt of RTE in Route Table but otherwise unreferenced. 

//
// Type of function pointer yielding distance between a pair of values.
//
typedef unsigned __int64 pFuncUi64Distance(unsigned __int64 x, unsigned __int64 y);

//* RouteTableInit
//
//  Initializes a Route Table.
//
void
RouteTableInit(RouteTable *RT)
{
    KeInitializeSpinLock(&RT->Lock);
    RT->FirstRTE = RT->LastRTE = SentinelRTE(RT);
    RT->NextPathId = GetRandomNumber(0xFFFFFFFF);
}

//* AddRefRTE
void
AddRefRTE(RouteTableEntry *RTE)
{
    InterlockedIncrement(&RTE->RefCnt);
}

//* ReleaseRTE
void
ReleaseRTE(RouteTableEntry *RTE)
{
    if (InterlockedDecrement(&RTE->RefCnt) == 0) {
        //
        // Release any NCE and NTE refs held by the RTE.
        // Then free the RTE itself.
        //
        VRRASSERT(VRR_RTE_STATE_ORPHAN == RTE->State);
        if (NULL != RTE->A.Next)
            ReleaseNCE(RTE->A.Next);
        if (NULL != RTE->B.Next)
            ReleaseNCE(RTE->B.Next);
        if (NULL != RTE->A.NTE)
            ReleaseNTE(RTE->A.NTE);
        if (NULL != RTE->B.NTE)
            ReleaseNTE(RTE->B.NTE);

        ExFreePool(RTE);
    }
}

//* RemoveRTE
//
//  Remove an RTE from a miniport's Route Table.
//  Caller must hold the RT lock for the virtual adapter.
//
void
RemoveRTE(
    RouteTable *RT,
    RouteTableEntry *RTE)
{
    VRRASSERT(RTE != (RouteTableEntry *)RT);
    VRRASSERT(RTE->RefCnt >= 2);     // Refs 2 used in RT links. There may be others.
    VRRASSERT(VRR_RTE_STATE_ORPHAN != RTE->State);
    
    RTE->State = VRR_RTE_STATE_ORPHAN;

    RTE->Next->Prev = RTE->Prev;
    ReleaseRTE(RTE);

    RTE->Prev->Next = RTE->Next;

    ReleaseRTE(RTE);
    InterlockedDecrement(&RT->Count);
}

//* RouteTableCleanup
//
//  Uninitializes a Route Table.
//
void
RouteTableCleanup(RouteTable *RT)
{
    RouteTableEntry *RTE;

    while ((RTE = RT->FirstRTE) != SentinelRTE(RT)) {
        //
        // Remove the RTE.
        //
        RemoveRTE(RT,RTE);
    }
}

//* NewPathId
//
//  Guaranteed unique within the set (self,PathId).
//
//  Caller must hold the RT->Lock.
//
uint
NewPathId(RouteTableEntry *RTE)
{
    //
    // Guaranteed unique for lifetime of RTE.
    //
    return (uint)RTE;
}

//* CreateRTE
//
//  Allocate and initialize a new RTE in memory.
//
//  Caller must not hold the NC->Lock.
//
RouteTableEntry *
CreateRTE(
    MiniportAdapter *VA,
    const VirtualAddress EndpointA,
    const VirtualAddress EndpointB,
    uint PathId,
    const VirtualAddress NextA,
    VRRIf LocIFa,
    VRRIf RemIFa,
    const VirtualAddress NextB,
    VRRIf LocIFb,
    VRRIf RemIFb,
    VirtualAddress NextNextA)
{
    RouteTableEntry *RTE;
    NeighborCache *NC = &VA->NC;
    NeighborCacheEntry *NCEa = NULL;
    NeighborCacheEntry *NCEb = NULL;
    KIRQL OldIrql;
    RTEFlags Flags;
    Flags.Flags = 0;

    VRRASSERT(! IsUnspecified(EndpointA));
    VRRASSERT(! IsUnspecified(EndpointB));
    VRRASSERT(! VirtualAddressEqual(EndpointA,EndpointB));    
    VRRASSERT(VirtualAddressEqual(VA->Address,EndpointA) || !IsUnspecified(NextA));
    VRRASSERT(VirtualAddressEqual(VA->Address,EndpointB) || !IsUnspecified(NextB));
    VRRASSERT(LocIFa != VRR_IFID_UNSPECIFIED || IsUnspecified(NextA));
    VRRASSERT(RemIFa != VRR_IFID_UNSPECIFIED || IsUnspecified(NextA));
    VRRASSERT(LocIFb != VRR_IFID_UNSPECIFIED || IsUnspecified(NextB));
    VRRASSERT(RemIFb != VRR_IFID_UNSPECIFIED || IsUnspecified(NextB));
    VRRASSERT(VRR_PATHID_UNSPECIFIED != PathId || VirtualAddressEqual(VA->Address,EndpointA));
    //
    // Next two assertions taken from from ns2 emulation ForwardingTable.cs::AddEntry
    // Debug.VRRASSERT(node.nodeid != fte.EndPointA || fte.NextA == node.nodeid);
    // Debug.VRRASSERT(node.nodeid != fte.EndPointB || fte.NextB == node.nodeid);
    //
    VRRASSERT(!VirtualAddressEqual(VA->Address,EndpointA) || IsUnspecified(NextA));
    VRRASSERT(!VirtualAddressEqual(VA->Address,EndpointB) || IsUnspecified(NextB));
        
    //
    // An NCE must exist in state LINKED for either or both of NextA and NextB.
    //
    KeAcquireSpinLock(&VA->NC.Lock, &OldIrql);
    
    if (! IsUnspecified(NextA))
        NCEa = FindNCE(NC,NextA,LocIFa, RemIFa, VRR_NCE_STATE_LINKED);
        
    if (NULL != NCEa)
        AddRefNCE(NCEa);

    if (! IsUnspecified(NextB))
        NCEb = FindNCE(NC,NextB,LocIFb, RemIFb, VRR_NCE_STATE_LINKED);
    
    if (NULL != NCEb)
        AddRefNCE(NCEb);

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

    //
    // We must have an NCE for any non-NULL next hops.
    //
    if (NULL == NCEa && ! IsUnspecified(NextA))
        goto ErrorReleaseNCEandReturn;
    if (NULL == NCEb && ! IsUnspecified(NextB))
        goto ErrorReleaseNCEandReturn;

    //
    // The NCE have been found and we have refs on them.
    //
    RTE = ExAllocatePool(NonPagedPool, sizeof *RTE);
    if (RTE == NULL)
        goto ErrorReturn;

    //
    // Initialize the RTE.
    //
    RtlZeroMemory(RTE, sizeof *RTE);
    RtlCopyMemory(RTE->A.Address, EndpointA, sizeof(VirtualAddress));
    RtlCopyMemory(RTE->B.Address, EndpointB, sizeof(VirtualAddress));
    RTE->A.uint64Address = VirtualAddressToUint64(EndpointA);
    RTE->B.uint64Address = VirtualAddressToUint64(EndpointB);
    RTE->State = VRR_RTE_STATE_ACTIVE;
    RTE->A.Next = NCEa;
    RTE->B.Next = NCEb;
    RtlCopyMemory(RTE->NextNextA, NextNextA, sizeof(VirtualAddress));

    //
    // If the path originates locally (we are endpoint A) then assign
    // a new PathId, quaranteed unique within the PathIds at this node.
    //
    if (VirtualAddressEqual(VA->NT.Self->Address, EndpointA)) {
        VRRASSERT(VRR_PATHID_UNSPECIFIED == PathId);
        RTE->PathId = NewPathId(RTE);
    } else {
        VRRASSERT(VRR_PATHID_UNSPECIFIED != PathId);
        RTE->PathId = PathId;
    }

    //
    // If either or both endpoint is in the node table, keep a pointer to it.
    //
    KeAcquireSpinLock(&VA->NT.Lock, &OldIrql);
    
    RTE->A.NTE = FindNTE(&VA->NT,EndpointA);
    if (NULL != RTE->A.NTE) {
        AddRefNTE(RTE->A.NTE);
    }
        
    RTE->B.NTE = FindNTE(&VA->NT,EndpointB);
    if (NULL != RTE->B.NTE) {
        AddRefNTE(RTE->B.NTE);
    }
    
    RTE->Flags = Flags;
    
    KeReleaseSpinLock(&VA->NT.Lock, OldIrql);

    return RTE;
    
ErrorReleaseNCEandReturn:

    if (NULL != NCEa)
       ReleaseNCE(NCEa);
    if (NULL != NCEb)
       ReleaseNCE(NCEb);
       
ErrorReturn:
    return NULL;
       
}

//* InsertRTE
//
//  Insert RTE into the (ordered) list for given RT.
//
//  Caller must hold the RT->Lock.
//
void
InsertRTE(
    RouteTable *RT,
    RouteTableEntry *RTE)
{
    RouteTableEntry *RTENext;

    VRRASSERT(RT != NULL);
    VRRASSERT(RTE != NULL);
#if DBG
    //VRRASSERT(NULL == FindNCE(NC, NCE->VAddress, NCE->LocIF, NCE->InIf, VRR_NCE_STATE_ANY));
#endif 

    //
    // Find insertion point for new RTE in the Route Table.
    //
    RTENext = RT->FirstRTE;
    for (RTENext = RT->FirstRTE; 
         RTENext != SentinelRTE(RT);
         RTENext = RTENext->Next) {
        if (VirtualAddressLessThan(RTENext->A.Address, RTE->A.Address))
            continue;
            
        // DBG: check for duplicate RTE, i.e. RTE already exists.
        VRRASSERT(! VirtualAddressEqual(RTE->A.Address, RTENext->A.Address) ||
               RTE->A.LocIF != RTENext->A.LocIF ||
               RTE->A.RemIF != RTENext->A.RemIF ||
               RTE->A.Next != RTENext->A.Next ||
               ! VirtualAddressEqual(RTE->B.Address, RTENext->B.Address) ||
               RTE->B.LocIF != RTENext->B.LocIF ||
               RTE->B.RemIF != RTENext->B.RemIF ||
               RTE->B.Next != RTENext->B.Next ||
               RTE->PathId != RTENext->PathId ||
               RTE->Flags.Flags != RTENext->Flags.Flags ||
               RTENext->State == VRR_RTE_STATE_RETIRED);
        //
        // Insert the new RTE immediately prior to NextRTE.
        //
        break;
    }

    //
    // Insert the new RTE into the Route table.
    //
    RTE->Prev = RTENext->Prev;
    RTE->Prev->Next = RTE;
    AddRefRTE(RTE);
    RTE->Next = RTENext;
    RTE->Next->Prev = RTE;
    AddRefRTE(RTE);
    
    InterlockedIncrement(&RT->Count);

}


//* RouteFindValidRoute
//
// Find a valid route from the Route table.
//
// Caller must hold the Route table lock.
//
RouteTableEntry *
RouteFindValidRoute(
    RouteTable *RT,
    const VirtualAddress EndpointA,
    const VirtualAddress EndpointB)
{
    RouteTableEntry *RTE = NULL;

    //
    // For now we just return the first valid route encountered.
    //
    for (RTE = RT->FirstRTE; RTE != SentinelRTE(RT); RTE = RTE->Next)
        if (VirtualAddressEqual(RTE->A.Address, EndpointA))
        if (VirtualAddressEqual(RTE->B.Address, EndpointB))
        if (VRR_RTE_STATE_ACTIVE == RTE->State)
            return RTE;
    
    return NULL;
}

//* FindRTE
//
// Find an RTE of state=ACTIVE in the Route table.
//
// Caller must hold the Route table lock.
//
RouteTableEntry *
FindRTE(
    MiniportAdapter *VA,
    const VirtualAddress EndpointA,
    const VirtualAddress EndpointB,
    uint PathId,
    const VirtualAddress NextA,
    VRRIf LocIFa,
    VRRIf RemIFa,
    const VirtualAddress NextB,
    VRRIf LocIFb,
    VRRIf RemIFb,
    RTEFlags Flags)
{
    RouteTable *RT = &VA->RT;
    NeighborCache *NC = &VA->NC;
    RouteTableEntry *RTE = NULL;

    for (RTE = RT->FirstRTE; RTE != SentinelRTE(RT); RTE = RTE->Next)
        if (VRR_RTE_STATE_ACTIVE == RTE->State)
        if (VirtualAddressEqual(RTE->A.Address, EndpointA))
        if (VirtualAddressEqual(RTE->B.Address, EndpointB))
        if (VRR_PATHID_UNSPECIFIED == PathId || RTE->PathId == PathId) {

            uint MatchNextA = FALSE;
            uint MatchNextB = FALSE;
            
            //
            // The RTE must match the callers Flags argument.
            //
            if (RTE->Flags.Flags != Flags.Flags)
                continue;
        
            //
            // Check for matching NextHop addresses.
            //
            if (IsUnspecified(NextA)) {
                MatchNextA = TRUE;
            } else if (RTE->A.Next != NULL) {
                NeighborCacheEntry *NCE = RTE->A.Next;
                
                KeAcquireSpinLockAtDpcLevel(&VA->Lock);
                if (VirtualAddressEqual(NCE->VAddress,NextA))
                if (LocIFa == VRR_IFID_UNSPECIFIED || NCE->LocIF == LocIFa)
                if (RemIFa == VRR_IFID_UNSPECIFIED || NCE->RemIF == RemIFa)
                    MatchNextA = TRUE;
                KeReleaseSpinLockFromDpcLevel(&VA->Lock);
            }
            if (IsUnspecified(NextB)) {
                MatchNextB = TRUE;
            } else if (RTE->B.Next != NULL) {
                NeighborCacheEntry *NCE = RTE->B.Next;
            
                KeAcquireSpinLockAtDpcLevel(&VA->Lock);
                if (VirtualAddressEqual(NCE->VAddress,NextB))
                if (LocIFb == VRR_IFID_UNSPECIFIED || NCE->LocIF == LocIFb)
                if (RemIFb == VRR_IFID_UNSPECIFIED || NCE->RemIF == RemIFb)
                    MatchNextB = TRUE;
                KeReleaseSpinLockFromDpcLevel(&VA->Lock);
            }
            
            //
            // If RTE meets all constraints, we are done.
            //
            if (MatchNextA && MatchNextB)
                return RTE;
                
        }
    
    //
    // Did not find a matching RTE.
    //
    return NULL;
}


//* FindOrCreateRTE
//
//  Finds or creates a Route table entry.
//  Caller must hold the Route table lock.
//
RouteTableEntry *
FindOrCreateRTE(
    MiniportAdapter *VA,
    const VirtualAddress EndpointA,
    const VirtualAddress EndpointB,
    uint PathId,
    const VirtualAddress NextA,
    VRRIf LocIFa,
    VRRIf RemIFa,
    const VirtualAddress NextB,
    VRRIf LocIFb,
    VRRIf RemIFb,
    VirtualAddress NextNextA,
    RTEFlags Flags)
{
    RouteTable *RT = &VA->RT;
    RouteTableEntry *RTE;
    RouteTableEntry *RTENext;

    //
    // Should NextNextA be part of RTE key? For now not, pending local path repair implementation.
    //
    RTE = FindRTE(VA, EndpointA, EndpointB, PathId, NextA, LocIFa, RemIFa, NextB, LocIFb, RemIFb,Flags);
    
    if (RTE != NULL)
        return RTE;
        
    //
    // Create a new RTE.
    //
    RTE = CreateRTE(VA, EndpointA, EndpointB, PathId, NextA,
                    LocIFa, RemIFa, NextB, LocIFb, RemIFb, NextNextA);
    if (NULL == RTE)
        return NULL;

    //
    // Insert the RTE into the Route table.
    //
    RTE->Flags = Flags;
    InsertRTE(RT,RTE);

    return RTE;
}

//* RTERetireTimeout
//
//  Returns the appropriate retirement period for a 
//  given type of RTE.
//
Time
RTERetireTimeout(
    RTEFlags Flags)
{
    Time Now = KeQueryInterruptTime();

#if gregos // for debugging only, enable this to preserve TDCE and retired RTE 
    if (Flags.VSet == 1)
        return Now + RTE_VSET_RETIREMENT;
#endif

    return Now + RTE_RETIRED_TIMEOUT;
}

//* RouteTableTimeout
//
//  Housekeeping of Route Table.
//
Time
RouteTableTimeout(
    MiniportAdapter *VA,