neighbor.c

Vitual Ring Routing 管你知不知道

    // This may succeed in refreshing the SibInfo referenced below, whether
    // NdisRequest completes synchronously or asynchronously. Note that we 
    // cannot call ProtocolRequestHelper to initiate NdisRequests because we
    // must avoid blocking e.g. when the underlying 802.11 adapter is unloading.
    //
    for (i = 0; i < CountPA; i++) {
        NDIS_STATUS NdisStatus;
        ProtocolAdapter *PA = FindPhysicalAdapterFromIndex(VA, i+1);
        ProtocolRequest *Request;
        MSRCSibTableInfo *SibInfo;

        if (PA == NULL)
            continue;
        if (PA->SupportsQuerySibTable == FALSE)
            continue;

        if ((Request=ExAllocatePool(NonPagedPool, sizeof *Request))==NULL)
            continue;

        if ((SibInfo=ExAllocatePool(NonPagedPool, sizeof *SibInfo))==NULL) {
            ExFreePool(Request);
            continue;
        }

        RtlZeroMemory(Request,sizeof(*Request));

        Request->Request.RequestType = NdisRequestQueryInformation;
        Request->ContextOnStack = FALSE;
        Request->Request.DATA.QUERY_INFORMATION.Oid = OID_MSRC_QUERY_SIB_TABLE;
        Request->Request.DATA.QUERY_INFORMATION.InformationBuffer = SibInfo;
        Request->Request.DATA.QUERY_INFORMATION.InformationBufferLength = sizeof(*SibInfo);
        Request->PA = PA;
        Request->Buffer = SibInfo;
        NdisRequest(&NdisStatus, PA->Handle, &Request->Request);

        if (NdisStatus == NDIS_STATUS_PENDING) {
            continue;
        }
        else {
            //
            // ProtocolRequestComplete will not get called, so we free memory inline.
            //
            TranslateNdisRequestStatus(NdisStatus, i+1);
            ExFreePool(SibInfo);
            ExFreePool(Request);
        }
    }

    KeAcquireSpinLock(&VA->NC.Lock, &OldIrql);
    
    OldNCCount = VA->NC.Count;
    CountLinkedLast = VA->NC.CountLinked;

    for (NCE = VA->NC.FirstNCE;
         NCE != SentinelNCE(&VA->NC);
         NCE = NextNCE) {

        uint DownDateRoutes = FALSE;
        UCHAR QoSInput = 0;
        ProtocolAdapter *PA = FindPhysicalAdapterFromIndex(VA, NCE->LocIF);
        
        CheckCount++;

        VRRASSERT(NCE->RefCnt >= VRR_MIN_NCE_REFCNT);
        VRRASSERT(VRR_NCE_STATE_ORPHAN != NCE->State);

        NextNCE = NCE->Next;

        //
        // For link quality metric, if layer 2 driver supports it, 
        // we prefer OID_MSRC_QUERY_SIB_TABLE over packet pair.
        //
        if (PA != NULL &&
            PA->SupportsQuerySibTable == TRUE) {
            //
            // Adapter supports OID_MSRC_QUERY_SIB_TABLE.
            //
            MSRCSibTableInfo *SibInfo = &PA->SibInfo;
            uint Rssi = 0;

            NCE->Flags |= VRR_NCE_FLAG_SIB_OID;

            //
            // Serialize access to PA->SibInfo with NdisRequests
            // that may be running concurrently and search it for
            // an entry matching this neighbour.
            //
            KeAcquireSpinLockAtDpcLevel(&PA->SibInfoLock);
            for (i = 0; i < SibInfo->ActiveEntries; i++) {
                MSRCSibTableEntry *STE = (MSRCSibTableEntry *)&SibInfo->SibTable[i];
                if (VirtualAddressEqual(STE->MACAddr,NCE->PAddress)) {
                    Rssi = SibTableEntryToRSSI(STE);
                    NCE->BitsPerSec = STE->ETTtobps;
                    NCE->AveUsedBitsPerSecond = STE->AveTxBytes * 8;
                    break;
                }
            }
            KeReleaseSpinLockFromDpcLevel(&PA->SibInfoLock);

            //
            // The RSSI samples from Sib Table are smoothed using
            // a EWMA.
            //
            NCE->Rssi = ExpWeightedMovingAverage(NCE->Rssi,
                                                 Rssi,
                                                 SIB_OID_EWMA_ALPHA);

        }
        else if ((NCE->Flags & VRR_NCE_FLAG_SIB_OID) == 0 &&
                 NCE->LastWcettBandwidth != NCE->AdjOut.wcett.Bandwidth)
            //
            // Adapter does not support OID_MSRC_QUERY_SIB_TABLE, but
            // QoS modules have updated bandwidth estimate so we must
            // update our exp weighted moving average of same.
            //
            UpdateQoSForNCE(NCE);

        //
        // Check for NCE state transitions due to changed QoS.
        // Downgrade the state if appropriate. Upgrades are done
        // in Hello receive path.
        //
        QoSInput = QoSToNCEStateTransition(VA,NCE);

        if (NCE->State != VRR_NCE_STATE_FAILED &&
            QoSInput == VRR_NCE_INPUT_QoS_EVICT) {
            //
            // QoS has dropped below threshold: fail the link.
            //
            VrrKdPrint("NCETimeout: QoSEVICT: NCE(d)=>FAILED",NULL,NCE->VAddress);
            NCE->CountFailQoSEvict++;
            FailNCE(NCE, Now);
            DownDateRoutes = TRUE;
        }
        else if (NCE->State != VRR_NCE_STATE_FAILED &&
                 NCE->TimeLastHello + HELLO_LIFETIME < Now) {
            //
            // Fail the link if we've stopped hearing Hello messages from peer.
            //
            VrrKdPrint("NCETimeout: stopped hearing hellos: NCE(d)=>FAILED",NULL,NCE->VAddress);
            NCE->CountFailHelloLoss++;
            FailNCE(NCE, Now);
            DownDateRoutes = TRUE;
        }
        else if ((NCE->Flags & VRR_NCE_FLAG_SIB_OID) &&
                 NCE->LastUnicastCompletion + IDLE_PROBE_TIMEOUT < Now) {
            //
            // Occassionally probe an idle 802.11 link with a small packet.
            //
            if (VA->TxDropAllButHello == FALSE)
            if (PktPairCreateProbePacket(VA, &NCE->AdjOut, 0, &Probe, 0, TRUE, 
                                         METRIC_TYPE_INVALID) == NDIS_STATUS_SUCCESS) {
                PC(Probe)->OrigPacket = ProbeList;
                ProbeList = Probe;
                VrrTrace(VA,3,"NC:TO=periodic probe of idle unicast link",NULL,NULL,NCE->VAddress,NULL,0,NULL,0);
            }
        }
        else if (NCE->State == VRR_NCE_STATE_FAILED &&
                 NCE->Timeout < Now) {
            //
            // Peer should have detected link failure by now.
            // Attempts to recover the link may begin as soon
            // as the link meets the QoS criteria.
            //
            NCE->Timeout = 0;
        }

        if (NCE->State & VRR_NCE_STATE_LINKED)
            CountLinkedNow++;

        if (NCE->State == VRR_NCE_STATE_FAILED &&
            NCE->Timeout == 0) {
            if (QoSInput == VRR_NCE_INPUT_QoS_ADMIT) {
                //
                // We are not delaying transition from FAILED
                // and QoS is above the admission threshold.
                // Start to advertise the link.
                //
                NCE->State = VRR_NCE_STATE_PENDING;
            }
            else if (WcettIsInfinite(NCE->AdjOut.Metric)) {
                //
                // Release the NCE when ETX has given up on it.
                //
                VrrTrace(VA,3,"NCETimeout: WcettIsInfinite: RemoveNCE(d)",NCE->VAddress,NULL,NULL,NULL,0,NULL,0);
                RemoveNCE(&VA->NC,NCE);
                continue;
            }
        }

        if (DownDateRoutes) {
            //
            // Downdate the Route Table wrt this NCE.
            //
            RouteFailLink(VA,NCE);
            continue;
        }
    }

    VRRASSERT(CheckCount == OldNCCount);
    VA->NC.CountLinked = CountLinkedNow;

    KeReleaseSpinLock(&VA->NC.Lock, OldIrql);
    
    //
    // Send occasional probes on idle 802.11 links.
    //
    while ((Probe = ProbeList) != NULL) {
        ProbeList = PC(Probe)->OrigPacket;
        PC(Probe)->OrigPacket = NULL;

        if (PC(Probe)->PA == NULL)
            PktPairSendProbeComplete(VA, Probe, NDIS_STATUS_FAILURE);
        else
            ProtocolTransmit(PC(Probe)->PA, Probe);
    }

    //
    // If we have just detected loss of our last link then purge state and
    // unilaterally launch a singleton ring of our own, i.e. exit ring.
    //
    // Ref C# "FailAllNeighbors(); // This will kick everything off again"
    //
    if (CountLinkedNow == 0 && CountLinkedLast != 0 &&
        IsJoiningOnHold(VA) == FALSE &&
        IsDriverInitialized(VA) == TRUE) {

        VrrTrace(VA,2,"gregos: NCETimeout exit ring => FailAllAndChangeState",NULL,NULL,NULL,NULL,0,NULL,0);
        FailAllNeigboursAndChangeState(VA,IsPartitionRepairEnabled(VA));
        InterlockedIncrement((PLONG)&VA->CountExitNCE);
        SendHellos(VA, Now);
    }

    if (NextTimeout > Now + MIN_NCE_TIMOUT_INTERVAL)
        NextTimeout = Now + MIN_NCE_TIMOUT_INTERVAL;

    return NextTimeout;
}

//*RandomPhysicalNeighbor
//
//  Randomly select a physical neighbor, for example to serve as a proxy.
//
//  Returns TRUE iff a physical neighbor was found.
//
//  Caller must not hold NC->Lock.
//
boolint
RandomPhysicalNeighbor(
    MiniportAdapter *VA,
    VirtualAddress NeighborAddress)
{
    KIRQL OldIrql;
    NeighborCacheEntry *NCE;
    uint NumActive = 0;    
    uint Chosen;
    boolint FoundNCE;

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

    //
    // Find number of ACTIVE neighbors.
    // gregos: better to maintain a counter of these somewhere.
    //
    for (NCE = VA->NC.FirstNCE; NCE != SentinelNCE(&VA->NC); NCE = NCE->Next) {
         
        if (NCE->State == VRR_NCE_STATE_ACTIVE)
            NumActive++;
    }

    if (NumActive == 0) {
        FoundNCE = FALSE;
        goto ReleaseAndReturn;
    }
    FoundNCE = TRUE;

    //
    // Randomly choose integer in range [0,NumActive-1].
    //
    Chosen = GetRandomNumber(NumActive - 1) + 1;
    
    //
    // Get details from NCE of the chosen neighbor.
    //
    for (NCE = VA->NC.FirstNCE;
         NCE != SentinelNCE(&VA->NC);
         NCE = NCE->Next) {
         
        if (NCE->State != VRR_NCE_STATE_ACTIVE)
            continue;
        
        if (--Chosen == 0) {
            RtlCopyMemory(NeighborAddress,NCE->VAddress,sizeof(VirtualAddress));
            break;
        }
    }
    
ReleaseAndReturn:
    KeReleaseSpinLock(&VA->NC.Lock, OldIrql);
    
    return FoundNCE;
}

//* QoSToNCEStateTransition
//
//
UCHAR
QoSToNCEStateTransition(
    MiniportAdapter *VA,
    NeighborCacheEntry *NCE)
{
    uint Bandwidth;
    uint LossProb;
    uint Rssi;
    uint RateAdmitThreshold = InterlockedCompareExchange(&VA->RateAdmitThreshold,0,0);
    uint RateEvictThreshold = InterlockedCompareExchange(&VA->RateEvictThreshold,0,0);
    uint RssiAdmitThreshold = InterlockedCompareExchange(&VA->RssiAdmitThreshold,0,0);
    uint RssiEvictThreshold = InterlockedCompareExchange(&VA->RssiEvictThreshold,0,0);
    
    LossProb = NCE->AdjOut.wcett.LossProb;
    Bandwidth = NCE->BitsPerSec;
    Rssi = NCE->Rssi;

    //
    // We use distinct admission and eviction thresholds in order to
    // prevent rapid fluctuations in QoS from destabilizing NCE states.
    //
    VRRASSERT(EtxAdmitMin < EtxEvictMin); 
    VRRASSERT(RATE_EVICT_DEFAULT < RATE_ADMIT_DEFAULT); 
    VRRASSERT(RateEvictThreshold < RateAdmitThreshold);
    VRRASSERT(RSSI_EVICT_DEFAULT < RSSI_ADMIT_DEFAULT); 
    VRRASSERT(RssiEvictThreshold < RssiAdmitThreshold);

    //
    // Transition beyond FAILED iff all above admission threshold.
    //
    if (LossProb < EtxAdmitMin && Bandwidth >= RateAdmitThreshold) {
        if ((NCE->Flags & VRR_NCE_FLAG_SIB_OID) == 0)
            return VRR_NCE_INPUT_QoS_ADMIT;
        else if (Rssi >= RssiAdmitThreshold)
            return VRR_NCE_INPUT_QoS_ADMIT;
    }

    //
    // Transition to FAILED iff any below eviction threshold. 
    //
    if (LossProb >= EtxEvictMin)
        return VRR_NCE_INPUT_QoS_EVICT;
    if (Bandwidth < RateEvictThreshold)
        return VRR_NCE_INPUT_QoS_EVICT;
    if ((NCE->Flags & VRR_NCE_FLAG_SIB_OID) &&
        Rssi < RssiEvictThreshold)
        return VRR_NCE_INPUT_QoS_EVICT;
        
    return VRR_NCE_INPUT_QoS_NOOP;
}

//* SalvagePacketsFromMaintBuf
//
//  Salvage any (MB) packets for a given NCE.
//
//  In particular if NCE transitions from state ACTIVE we
//  do not want to leave stale messages queued against an
//  MBN that might get transmitted if NCE reconnects.
//
//  Caller must not hold MaintBuf->Lock.
//
void
SalvagePacketsFromMaintBuf(
    MiniportAdapter *VA,
    VirtualAddress Address,
    VRRIf LocIF,
    VRRIf RemIF)
{
    KIRQL OldIrql;
    MaintBuf *MB = VA->MaintBuf;
    MaintBufNode *MBN;
    Time Now = KeQueryInterruptTime();
    
    //
    // If there is a MBN matching the supplied arguments
    // then set its timeout to an expired value. 
    //
    KeAcquireSpinLock(&VA->MaintBuf->Lock, &OldIrql);
    MBN = MaintBufFindNode(MB, Address, LocIF, RemIF);
    if (MBN != NULL)
        MBN->LastAckRcv = Now - MAINTBUF_LINK_TIMEOUT - 1;
    KeReleaseSpinLock(&VA->MaintBuf->Lock, OldIrql);

    //
    // Cause MaintBufTimer to salvage any packets
    // attched to the MBN.
    //
    MaintBufTimer(VA,Now);
    
    VrrKdPrint("SalvagePacketsForNCE: dropped all pkts queued for s", Address, NULL);

}

//* FailNCE
//
// Set and NCE to status FAILED.
//
void
FailNCE(
    NeighborCacheEntry *NCE,
    Time Now)
{
    NCE->State = VRR_NCE_STATE_FAILED;
    NCE->Timeout = Now + HelloFailTimeout;
}

//* FailAllNCE
//
// Sets all NCE to status FAILED.
//
// Caller must not hold NC->Lock.
//
void
FailAllNCE(
    NeighborCache *NC,
    Time Now)
{
    KIRQL OldIrql;
    NeighborCacheEntry *NCE = NULL;

    KeAcquireSpinLock(&NC->Lock, &OldIrql);
    for (NCE = NC->FirstNCE; NCE != SentinelNCE(NC); NCE = NCE->Next) {
        FailNCE(NCE, Now);
    }
    KeReleaseSpinLock(&NC->Lock, OldIrql);
}

//* SaveCompletionTime
//
//  Maintain NCE->LastUnicastCompletion.
//
void
SaveCompletionTime(
    MiniportAdapter *VA,
    PNDIS_PACKET Packet,         // Packet that was sent.
    NDIS_STATUS Status)          // Final status of send.
{
    SRPacket *srp = NULL;

    if (! VRR_IDLE_UNICAST_PROBE)
        return;

    //
    // Data packet completion.
    //
    if (PC(Packet)->TransmitComplete == MaintBufStaticSendComplete ||
        PC(Packet)->TransmitComplete == PktPairSendProbeComplete)
        srp = PC(Packet)->srp;

    //
    // Control packet completion, i.e. originating from MaintBuf.
    //
    if (PC(Packet)->TransmitComplete == MaintBufTransmitComplete) {
        MaintBufPacket *MBP = PC(Packet)->MBP;
        if (MBP != NULL)
            srp = MBP->srp;
    }

    if (srp == NULL)
        return;

    //
    // Update timestamp for the NCE that sent this packet.
    // gregos: review: keep *NCE,AddRef(NCE) in SRP and skip locking?
    //
    if (Status == NDIS_STATUS_SUCCESS) {
        KIRQL OldIrql;
        NeighborCacheEntry *NCE;

        KeAcquireSpinLock(&VA->NC.Lock, &OldIrql);
        NCE = FindNCE(&VA->NC, 
                      srp->Token.NextVAddress,
                      srp->Token.LocIF,
                      srp->Token.RemIF,
                      VRR_NCE_STATE_ANY);

        if (NCE != NULL)
            NCE->LastUnicastCompletion = KeQueryInterruptTime();

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