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

//* VrrHelloInit
//
//  Called by MiniportInitialize.
//
void VrrHelloInit(
    MiniportAdapter *VA)
{
    Time Now = KeQueryInterruptTime();
    
    VA->VrrHelloParams.HelloTimeout = Now + HELLO_FREQUENCY;
    KdPrint(("VRR!VrrHelloInit(%p) - done.\n", VA));
}

//* VrrCreateHelloPacket
//
//  Creates a packet to send a hello.
//
static NDIS_STATUS
VrrCreateHelloPacket(
    MiniportAdapter *VA,
    Time Timestamp,
    SRPacket **ReturnPacket,
    uint Seq)
{
    SRPacket *SRP;
    NDIS_STATUS Status;
    const static VirtualAddress HelloDest = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
    uint VrrHelloSize;
    NeighborCacheEntry *NCE;
    NodeTableEntry *NTE;
    KIRQL OldIrql;
    uint NCECount = 0;
    uint i;
    uchar NTEState = 0;
    uint ZRouteSeqNo;

    InterlockedIncrement((unsigned long *)&VA->CountSendHello);

    //
    // Initialize an SRPacket for the Hello packet.
    // The Probe carries no data so it does not need an IV.
    //
    SRP = ExAllocatePool(NonPagedPool, sizeof *SRP);
    if (SRP == NULL) {
        return NDIS_STATUS_RESOURCES;
    }
    RtlZeroMemory(SRP, sizeof *SRP);

    //
    // Cache the state of our own (self) NTE.
    //
    if (IsDriverInitialized(VA))
        NTEState |= VRR_NTE_STATE_INITIALIZED;
    if (IsDriverActive(VA))
        NTEState |= VRR_NTE_STATE_ACTIVE;

    //
    // Lock the Neighbor cache during our traversals.
    //
    KeAcquireSpinLock(&VA->NC.Lock, &OldIrql);

    //
    // Obtain memory for VrrHello option. Include as many neighbours
    // as a single packet can accommodate.
    //
    NCECount = min(VA->NC.Count, VRRHELLO_MAX_NCE(VA));
    VrrHelloSize = sizeof *SRP->VrrHello               // Internal option linkage.
                   + sizeof(VrrHello)                  // Preamble.
                   + (NCECount * sizeof(VrrHelloNCE)); // List of NCE.
                   
    SRP->VrrHello = ExAllocatePool(NonPagedPool, VrrHelloSize);
    if (SRP->VrrHello == NULL) {
        Status = NDIS_STATUS_RESOURCES;
        goto FreeSRPAndExit;
    }
    
    RtlZeroMemory(SRP->VrrHello, VrrHelloSize);

    //
    // Initialize the source & destination of this packet.
    //
    RtlCopyMemory(SRP->Source, VA->Address, sizeof(VirtualAddress));
    RtlCopyMemory(SRP->Dest, HelloDest, sizeof(VirtualAddress));
    RtlCopyMemory(SRP->Origin, VA->Address, sizeof(VirtualAddress));
    SRP->FrameSeqNo = InterlockedIncrement((unsigned long *)&VrrGlobal.NextFrameSeqNo);
    SRP->HopCount = 0;

    //
    // Format the VrrHello header.
    // Note VrrBroadcastHello() will adjust Opt.SentFromIF before tx on each phys adapter.
    //
    SRP->VrrHello->Opt.OptionType = VRR_OPTION_TYPE_HELLO;
    SRP->VrrHello->Opt.OptDataLen = VRRHELLO_LEN(NCECount);
    RtlCopyMemory(SRP->VrrHello->Opt.source, VA->Address, sizeof(VirtualAddress));
    SRP->VrrHello->Opt.State = NTEState;

    //
    // Append list of NCE to the VrrHello header.
    //
    NCE = VA->NC.FirstNCE;
    for (i = 0; NCECount > 0; i++) {
        WCETTMetric *wcett = (WCETTMetric *)&NCE->AdjOut.Metric;
        ushort Rcvd = (ushort)NCE->AdjIn.MetricInfo.Wcett.Etx.ProbeHistorySZ;

        PVrrHelloNCE HNCE = &SRP->VrrHello->Opt.NCEList[i];
        RtlCopyMemory(&HNCE->addr, &NCE->VAddress, sizeof(VirtualAddress));
        HNCE->State = NCE->State;
        HNCE->LocIF = NCE->LocIF;
        HNCE->RemIF = NCE->RemIF; 
        HNCE->Rcvd = RtlUshortByteSwap(Rcvd);  
        HNCE->Mbps = BPS_TO_MBPS(NCE->BitsPerSec);
        HNCE->LossProb = wcett->LossProb >> 4; // Accuracy: 8-bit, compared to internal 12-bit.
        NCE = NCE->Next;
        NCECount--;
    }

    //
    // Finished with Neighbor cache. Release its lock.
    //
    KeReleaseSpinLock(&VA->NC.Lock, OldIrql);

    //
    // Insert Zero List into Hello option for partition repair protocol.
    //
    EmitHelloZeroList(VA, (VrrHello *)&SRP->VrrHello->Opt);

    //
    // Set the cleanup function.
    //
    SRP->TransmitComplete = VrrBroadcastSRPComplete;

    *ReturnPacket = SRP;
    return NDIS_STATUS_SUCCESS;

FreeSRPAndExit:
    KeReleaseSpinLock(&VA->NC.Lock, OldIrql);
    SRPacketFree(SRP);
    return Status;
}


//* SendHellos
//
//  Broadcasts a hello message across all phys adapters for a given virtual adapter. 
//
Time
SendHellos(
    MiniportAdapter *VA,
    Time Now)
{
    SRPacket *Packet;
    NDIS_STATUS Status;
    LARGE_INTEGER Timestamp;
    LARGE_INTEGER Frequency;
    Link *Adjacent;
    KIRQL OldIrql;
    NeighborCache *NC = &VA->NC;
    NeighborCacheEntry *NCE;

    if (VA->DriverLoadTime > Now) {
        VrrTrace(VA,2,"HI:Tx=enforce DriverLoadTime",NULL,NULL,NULL,
                      "TimeRemaining(ms)",TIME_TO_MS(VA->DriverLoadTime - Now),NULL,0);
        return Now + HELLO_FREQUENCY;
    }
    if (VA->TxDropAllHello != FALSE) {
        VrrTrace(VA,2,"HI:Tx=TxDropAllHello - supress tx hello",NULL,NULL,NULL,NULL,0,NULL,0);
        return Now + HELLO_FREQUENCY;
    }


    //
    // Create a hello packet, and send it. It is a broadcast packet,
    // so no need to loop through links individually. It will go out
    // on all links.
    //
    if (VA->VrrHelloParams.HelloTimeout <= Now) {
        //
        // Create a hello with current timestamp.
        //
        Timestamp = KeQueryPerformanceCounter(&Frequency);

        Status = VrrCreateHelloPacket(VA, Timestamp.QuadPart, &Packet, 0);

        if (Status == NDIS_STATUS_SUCCESS) {
            //
            // Send the packet.
            //
            //VrrKdPrint("SendHello",NULL,NULL);
            VrrBroadcastHello(VA, Packet);
        }

        VA->VrrHelloParams.HelloTimeout = Now + HELLO_FREQUENCY;

        VRRASSERT(VA->VrrHelloParams.HelloTimeout > Now);

        //
        // Recompute the ETX metric on all NCE. 
        //
        KeAcquireSpinLock(&NC->Lock, &OldIrql);
        for (NCE = NC->FirstNCE; NCE != SentinelNCE(NC); NCE = NCE->Next) {
            Adjacent = &NCE->AdjOut;
            WcettUpdateMetric(VA, Adjacent, FALSE);
            Adjacent->MetricInfo.Wcett.Etx.TotSentProbes++;
        }
        KeReleaseSpinLock(&NC->Lock, OldIrql);
    }
    
    return VA->VrrHelloParams.HelloTimeout;  
}

//* VrrComputeQoS
//
//  Calculates the WCETT metric over a two hop path
//  given the bandwidth in bps and probability of loss for
//  each hop in the path.
//
//  Mostly just a convenient wrapper for WCETT QoS routines.
//
uint
VrrComputeQoS(
    uint BandwidthA,
    uint LossProbA,
    uint BandwidthB,
    uint LossProbB)
{
    uint LinkMetricA = 0;
    uint LinkMetricB = 0;
    WCETTMetric *wcettA = (WCETTMetric *)&LinkMetricA;
    WCETTMetric *wcettB = (WCETTMetric *)&LinkMetricB;
    uint ETTA;
    uint ETTB;
    uint ETT;
    
    if (BandwidthA == 0)
        return (uint)-1;

    //
    // Encode bandwidth and loss probability per WCETT routines.
    //
    wcettA->Bandwidth = WcettEncodeBandwidth(BandwidthA);
    wcettA->LossProb = LossProbA;
    wcettB->Bandwidth = WcettEncodeBandwidth(BandwidthB);
    wcettB->LossProb = LossProbB;

    //
    // The caller may supply data for just one link (Hops1).
    //    
    if (WcettIsInfinite(LinkMetricA))
        return (uint)-1;
    ETTA = WcettConvETT(LinkMetricA);
    if (BandwidthB == 0 && LossProbB == 0)
        return ETTA;
    
    //
    // Calculate WCETT over the pair of links, ref WcettCalcWCETT().
    //
    if (WcettIsInfinite(LinkMetricB))
        return (uint)-1;

    //
    // This is simply the sum of ETT without WCETT weighting:
    // for now we do not consider multiple channels because
    // all our VRR test machines have only one radio for
    // transmission or reception for any physical neighbor.
    //
    ETTB = WcettConvETT(LinkMetricB);
    ETT = ETTA + ETTB;
    
    if (ETT < max(ETTA,ETTB))  // Overflow.
        return (uint)-1;

    return ETT;
    
}

//* ReceiveHello
//
//  Receive a VRR hello message. Called from ReceiveSRPacket.
//  Performs NeighborCache maintenance for Virtual Ring Routing.
//
//  Note: basic packet parsing performd in ReceiveSRPacket, which
//  provides us the VrrHello structure in an SRPacket option.
//
void
ReceiveHello(
    MiniportAdapter *VA,
    ProtocolAdapter *PA,
    SRPacket *srp)
{
    NeighborCacheEntry *NCE;
    KIRQL OldIrql;
    VRRIf SentFromIF;
    VirtualAddress *source;
    VRRIf LocIF = (VRRIf)PA->Index;
    Time Now = KeQueryInterruptTime();
    PVrrHelloNCE PHNCE = NULL;
    PVrrHelloNCE FirstHNCE = NULL;
    PVrrHelloNCE SelfHNCE = NULL;
    uint i;
    uint HNCELen;
    uint CountHNCE;
    uint SenderIsLinked = FALSE;
    uint SenderIsActive = FALSE;
    uint AttemptJoin = FALSE;
    TxToken Token;
    uchar SelfState;
    Time SelfTimeout;
    UCHAR SelfHNCEState = VRR_NCE_STATE_MISSING;
    UCHAR FSMInput = 0;
    UCHAR QoSInput = 0;
    UCHAR NCEStateOld;
    UCHAR NCEStateNew;
    uint Hop1LossProb;
    uint Hop1bps;
    Link *Adj;           // Holds ETX data.
    NDIS_PACKET *Probe = NULL;

    Now = KeQueryInterruptTime(); 

    //
    // Find start of NCEList in VrrHello message, and count of NCE in list.
    //    
    VRRASSERT(NULL != srp->VrrHello);
    SentFromIF = srp->VrrHello->Opt.SentFromIF;
    source = &srp->VrrHello->Opt.source;
    FirstHNCE = srp->VrrHello->Opt.NCEList;
    HNCELen = (uint)srp->VrrHello->Opt.OptDataLen
             + sizeof(srp->VrrHello->Opt.OptionType)
             + sizeof(srp->VrrHello->Opt.OptDataLen)
             - sizeof(VrrHello);
    CountHNCE = HNCELen / sizeof(VrrHelloNCE);

    //VrrKdPrint("Hello from",*source,NULL);
    
    //
    // Validate the VrrHello message.
    //
    if (HNCELen != CountHNCE * sizeof(VrrHelloNCE)) {
        VrrKdPrint("RcvHello: Len(NCEList) not multiple of size(NCE)",*source,NULL);
        return;
    }
    
    PHNCE = FirstHNCE;
    for (i = 0; i < CountHNCE; i++) {
        PHNCE = &FirstHNCE[i];
            
        if (PHNCE->State != VRR_NCE_STATE_FAILED &&
            PHNCE->State != VRR_NCE_STATE_PENDING &&
            PHNCE->State != VRR_NCE_STATE_LINKED &&
            PHNCE->State != VRR_NCE_STATE_ACTIVE) {
            KdPrint(("RcvHello: Invalid PHNCE state(%x) in VrrHello\n",PHNCE->State));
            VrrKdPrint("RcvHello:    sender of invalid PHNCE=s",*source,NULL);
            return;
        }
        if (PHNCE->RemIF == LocIF)
        if (PHNCE->LocIF == SentFromIF)
        if (VirtualAddressEqual(PHNCE->addr, VA->Address)) {
            SelfHNCE = PHNCE;
            SelfHNCEState = SelfHNCE->State;
            break;
        }
    }

    //
    // Find and update timestamps and state for the source of this hello.
    //
    KeAcquireSpinLock(&VA->NC.Lock, &OldIrql);
    
    if ((NCE = FindNCE(&VA->NC, *source, LocIF, SentFromIF, VRR_NCE_STATE_ANY)) == NULL)
        if ((NCE = CreateNCE(&VA->NC, *source, LocIF, SentFromIF)) == NULL)
            goto UnlockNCEAndReturn;

    //
    // Update phys addr.
    //
    RtlCopyMemory(NCE->PAddress, srp->EtherSource, sizeof(PhysicalAddress));
    NCE->TimeLastHello = Now;
    
    //
    // Update ETX data for this NCE.
    //
    Adj = &NCE->AdjIn;
    VRRASSERT(Adj->targetIndex == 0);
    Adj->MetricInfo.Wcett.Etx.TotRcvdProbes++;
    WcettAddProbe(VA, Adj);
    for (i = 0; i < CountHNCE; i++) {
        PHNCE = &FirstHNCE[i];
            
        if (VirtualAddressEqual(PHNCE->addr, VA->Address) &&
            PHNCE->LocIF == Adj->outif &&
            PHNCE->RemIF == Adj->inif) {

            //