neighbor.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.
//
// This file is derived from the Microsoft Research Mesh Connectivity Layer,
// available under the MSR-SSLA license, and downloadable from
// http://research.microsoft.com/mesh/.
//

#include "headers.h"
#define VRR_MIN_NCE_REFCNT    2     // RefCnt of NCE in Neigbor Cache but otherwise unreferenced. 

//* NeighborCacheInit
//
//  Initializes a neighbor cache.
//
void
NeighborCacheInit(NeighborCache *NC)
{
    KeInitializeSpinLock(&NC->Lock);
    NC->FirstNCE = NC->LastNCE = SentinelNCE(NC);
}

//* AddRefNCE
void
AddRefNCE(NeighborCacheEntry *NCE)
{
    InterlockedIncrement(&NCE->RefCnt);
}

//* ReleaseNCE
void
ReleaseNCE(NeighborCacheEntry *NCE)
{
    if (InterlockedDecrement(&NCE->RefCnt) == 0) {
        VRRASSERT(VRR_NCE_STATE_ORPHAN == NCE->State);
        ExFreePool(NCE);
    }
}

//* RemoveNCE
//
//  Remove an NCE from a miniport's neighbor cache.
//  Caller must hold the NC lock for the virtual adapter.
//
void
RemoveNCE(
    NeighborCache *NC,
    NeighborCacheEntry *NCE)
{
    VRRASSERT(NCE != (NeighborCacheEntry *)NC);
    VRRASSERT(NCE->RefCnt >= VRR_MIN_NCE_REFCNT);
    VRRASSERT(VRR_NCE_STATE_ORPHAN != NCE->State);
    
    NCE->State = VRR_NCE_STATE_ORPHAN;
    NCE->Next->Prev = NCE->Prev;
    ReleaseNCE(NCE);
    NCE->Prev->Next = NCE->Next;
    ReleaseNCE(NCE);

    InterlockedDecrement(&NC->Count);
}

//* NeighborCacheCleanup
//
//  Uninitializes a neighbor cache.
//
void
NeighborCacheCleanup(NeighborCache *NC)
{
    NeighborCacheEntry *NCE;

    while ((NCE = NC->FirstNCE) != SentinelNCE(NC)) {
        //
        // Remove the NCE.
        //
        RemoveNCE(NC,NCE);
    }
}

//* NeighborCacheFlushAddress
//
//  Removes entries from the neighbor cache.
//  If VAddr is NULL, removes all entries.
//  Otherwise it only removes entries for that virtual address.
//
void
NeighborCacheFlushAddress(
    NeighborCache *NC,
    const VirtualAddress VAddr,
    VRRIf RemIF)
{
    NeighborCacheEntry *NCE;
    NeighborCacheEntry *NextNCE;
    KIRQL OldIrql;

    KeAcquireSpinLock(&NC->Lock, &OldIrql);
    for (NCE = NC->FirstNCE;
         NCE != SentinelNCE(NC);
         NCE = NextNCE) {
        NextNCE = NCE->Next;

        //
        // Should we remove this NCE?
        //
        if ((VAddr == NULL) ||
            (VirtualAddressEqual(NCE->VAddress, VAddr) &&
             (NCE->RemIF == RemIF))) {
             
            RemoveNCE(NC,NCE);
        }
    }
    KeReleaseSpinLock(&NC->Lock, OldIrql);
}

//* FindNCE
//
// Find an NCE in the Neighbor cache.
//
// Caller must hold NC->Lock.
//
NeighborCacheEntry *
FindNCE(
    NeighborCache *NC,
    const VirtualAddress VAddr,
    VRRIf LocIF,
    VRRIf RemIF,
    uchar States)
{
    NeighborCacheEntry *NCE = NULL;

    for (NCE = NC->FirstNCE; NCE != SentinelNCE(NC); NCE = NCE->Next)
        if (VirtualAddressEqual(NCE->VAddress, VAddr) || IsUnspecified(VAddr))
        if (NCE->RemIF == RemIF || VRR_IFID_UNSPECIFIED == RemIF) 
        if (NCE->LocIF == LocIF || VRR_IFID_UNSPECIFIED == LocIF)
        if (NCE->State & States)
            return NCE;
    
    return NULL;
}

//* InsertNCE
//
//  Insert NCE into the (ordered) list for given NC.
//
//  Caller must hold the NC->Lock.
//
void
InsertNCE(
    NeighborCache *NC,
    NeighborCacheEntry *NCE)
{
    NeighborCacheEntry *NCENext;

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

    //
    // Find insertion point for new NCE in the Neighbor cache.
    //
    NCENext = NC->FirstNCE;
    for (NCENext = NC->FirstNCE; 
         NCENext != SentinelNCE(NC);
         NCENext = NCENext->Next) {
        if (VirtualAddressLessThan(NCENext->VAddress, NCE->VAddress))
            continue;
        if (VirtualAddressEqual(NCE->VAddress, NCENext->VAddress) && 
            NCENext->LocIF < NCE->LocIF)
            continue;
        if (VirtualAddressEqual(NCE->VAddress, NCENext->VAddress) &&
            NCENext->LocIF == NCE->LocIF && 
            NCENext->RemIF < NCE->RemIF)
            continue;
        //
        // We need to insert the new NCE immediately prior to NextNCE.
        //
        break;
    }

    //
    // Insert the new NCE into the cache.
    //
    NCE->Prev = NCENext->Prev;
    NCE->Prev->Next = NCE;
    AddRefNCE(NCE);
    NCE->Next = NCENext;
    NCE->Next->Prev = NCE;
    AddRefNCE(NCE);
    
    InterlockedIncrement(&NC->Count);
}

//* CreateNCE
//
//  Creates a new NCE and inserts it in neighbor cache.
//  Called with the neighbor cache locked.
//
NeighborCacheEntry *
CreateNCE(
    NeighborCache *NC,
    const VirtualAddress VAddr,
    VRRIf LocIF,
    VRRIf RemIF)
{
    NeighborCacheEntry *NCE;
    MiniportAdapter *VA;
    Time Now = KeQueryInterruptTime();

    //
    // Allocate memory for new NCE.
    //
    NCE = ExAllocatePool(NonPagedPool, sizeof *NCE);
    if (NCE == NULL)
        return NULL;

    //
    // Initialize the NCE. Our caller must initialize PAddress.
    //
    RtlZeroMemory(NCE, sizeof *NCE);  // Init NCE to zeros throughout.
    NCE->State = VRR_NCE_STATE_FAILED;
    RtlCopyMemory(NCE->VAddress, VAddr, sizeof(VirtualAddress));
    NCE->RemIF = RemIF;
    NCE->LocIF = LocIF;
    
    //
    // Init WCETT state of Link members.
    //
    VA = CONTAINING_RECORD(NC,MiniportAdapter,NC);
    NCE->AdjIn.outif = RemIF;
    NCE->AdjIn.inif = LocIF;
    NCE->AdjIn.TimeStamp = Now;
    NCE->AdjOut.TimeStamp = Now;
    WcettInitLinkMetric(VA,0,&NCE->AdjIn,Now);
    NCE->AdjOut.outif = LocIF;
    NCE->AdjOut.inif = RemIF;
    NCE->AdjOut.TimeStamp = Now;
    WcettInitLinkMetric(VA,0,&NCE->AdjOut,Now);

    //
    // Insert the NCE into the cache.
    //
    InsertNCE(NC,NCE);

    return NCE;

}

//* FindOrCreateNCE
//
//  Finds or creates a neighbor cache entry.
//  Called with the neighbor cache locked.
//
NeighborCacheEntry *
FindOrCreateNCE(
    NeighborCache *NC,
    const VirtualAddress VAddr,
    VRRIf RemIF,
    VRRIf LocIF)
{
    NeighborCacheEntry *NCE;

    NCE = FindNCE(NC, VAddr, LocIF, RemIF, VRR_NCE_STATE_ANY);
    if (NCE != NULL)
        return NCE;

    return CreateNCE(NC, VAddr, LocIF, RemIF);
    
}


//* NeighborFindPhysical
//
//  Given a virtual address and physical adapter,
//  finds a corresponding physical address.
//  Returns FALSE on failure.
//
boolint
NeighborFindPhysical(
    NeighborCache *NC,
    const VirtualAddress VAddr,
    VRRIf RemIF,
    PhysicalAddress PAddr)
{
    NeighborCacheEntry *NCE;
    KIRQL OldIrql;

    KeAcquireSpinLock(&NC->Lock, &OldIrql);
    for (NCE = NC->FirstNCE; ; NCE = NCE->Next) {
        if (NCE == SentinelNCE(NC)) {
            NCE = NULL;
            break;
        }

        //
        // Do we have an NCE for this virtual address?
        //
        if (VirtualAddressEqual(NCE->VAddress, VAddr) &&
            (NCE->RemIF == RemIF)) {
            //
            // Return the physical address.
            //
            RtlCopyMemory(PAddr, NCE->PAddress, sizeof(PhysicalAddress));
            break;
        }
    }
    KeReleaseSpinLock(&NC->Lock, OldIrql);
    return NCE != NULL;
}

//* UpdateQoSForNCE
//
//  Encapsulates our QoS calculations for physical neighbors.
//
void
UpdateQoSForNCE(
    NeighborCacheEntry *NCE)
{
    uint PktPairBandwidth = WcettDecodeBandwidth(NCE->AdjOut.wcett.Bandwidth);

    if (PktPairBandwidth > NCE->BitsPerSec) {
        //
        // Adopt PktPair estimate if it is greater than our running estimate.
        //
        NCE->BitsPerSec = PktPairBandwidth;
    }
    else {
        //
        // Exponential Weighted Moving Average for decreasing our running estimate.
        //
        uint Average;
        uint Sample;

        Average = NCE->BitsPerSec / PKT2_SCALING;
        Sample = PktPairBandwidth / PKT2_SCALING;
        Average = (Sample * PKT2_ALPHA) + ((PKT2_SCALING - PKT2_ALPHA) * Average );
        NCE->BitsPerSec = (uint)Average;
    }
    
    NCE->LastWcettBandwidth = NCE->AdjOut.wcett.Bandwidth;

}

//* SibTableEntryToRSSI
//
//  Returns freshest RSSI measurement from a SibTableEntry.
//
uint
SibTableEntryToRSSI(
    MSRCSibTableEntry *STE)
{
    uint MostRecentTimestamp = -1;
    uint MostRecentRssi = 0;

    //
    // Find the most recent of the valid RSSI indicators.
    //
    if (STE->rssiTime > 0) {
        MostRecentTimestamp = STE->rssiTime;
        MostRecentRssi = STE->rssiLast;
    }
    if (STE->rxUCastMSecs > 0 && STE->rxUCastMSecs < MostRecentTimestamp) {
        MostRecentTimestamp = STE->rxUCastMSecs;
        MostRecentRssi = STE->rxUCastRSSI;
    }
    if (STE->rxBeaconMSecs > 0 && STE->rxBeaconMSecs < MostRecentTimestamp) {
        MostRecentTimestamp = STE->rxBeaconMSecs;
        MostRecentRssi = STE->rxBeaconRSSI;
    }
    if (STE->rxBCastMSecs > 0 && STE->rxBCastMSecs < MostRecentTimestamp) {
        MostRecentTimestamp = STE->rxBCastMSecs;
        MostRecentRssi = STE->rxBCastRSSI;
    }

    //
    // Decay link quality if the most recent RSSI is stale.
    //
    // We start to decay link quality if we have heard
    // nothing during an interval that ought at least to
    // have included a hello.
    //
    if (MostRecentTimestamp > HelloMinFrequency)
        MostRecentRssi = 0;
    
    return MostRecentRssi;
}

//* ExpWeightedMovingAverage
//
//  Calculate exponentially weighted moving average of
//  two 32-bit unsigned ints according to a specified
//  alpha weight. We use 64-bit integer arithmetic. Note
//  that the intended alpha lies in the interval [0,0.99]
//  but is supplied as alpha*100, i.e. in interval [0,99].
//
uint
ExpWeightedMovingAverage(
    uint Average,
    uint Sample,
    uint Alpha)
{
    unsigned __int64 i64 = Average;
    i64 = (100 - Alpha)*i64;
    i64 += Alpha * Sample;
    i64 = i64 / 100;  // account for scaling of alpha.

    return (uint)i64;
}

//* TranslateNdisRequestStatus
//
//  Helper for NeighborCacheTimeout trace in debug builds.
//
void
TranslateNdisRequestStatus(
    NDIS_STATUS NdisStatus,
    uint PAIndex)
{
#if DBG
    if (NdisStatus == NDIS_STATUS_SUCCESS)
        KdPrint(("NCETimeoutOID PA(%u):  NdisStatus=NDIS_STATUS_SUCCESS\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_INVALID_OID)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_INVALID_OID\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_INVALID_LENGTH)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_INVALID_LENGTH\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_BUFFER_TOO_SHORT)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_BUFFER_TOO_SHORT\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_INVALID_DATA)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_INVALID_DATA\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_NOT_SUPPORTED)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_NOT_SUPPORTED\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_NOT_RECOGNIZED)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_NOT_RECOGNIZED\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_RESOURCES)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_RESOURCES\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_NOT_ACCEPTED)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_NOT_ACCEPTED\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_CLOSING)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_CLOSING\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_CLOSING_INDICATING)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_CLOSING_INDICATING\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_RESET_IN_PROGRESS)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_RESET_IN_PROGRESS\n",PAIndex));
    else if (NdisStatus == NDIS_STATUS_FAILURE)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=NDIS_STATUS_FAILURE\n",PAIndex));
    else if (NdisStatus == STATUS_INVALID_DEVICE_REQUEST)
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=STATUS_INVALID_DEVICE_REQUEST\n",PAIndex));
    else if (NdisStatus != NDIS_STATUS_SUCCESS) {
        KdPrint(("NCETimeoutOID PA(%u): silent mask NdisStatus=0x%8x\n",PAIndex,NdisStatus));
        VRRASSERT(FALSE);
    }
#else
    return;
#endif
}

//* NeighborCacheTimeout
//
//  Housekeeping of Neighbor cache.
//
Time
NeighborCacheTimeout(
    MiniportAdapter *VA,
    Time Now)
{
    NDIS_STATUS Status;
    LARGE_INTEGER Timestamp;
    LARGE_INTEGER Frequency;
    KIRQL OldIrql;
    Time NextTimeout = Now + MIN_NCE_TIMOUT_INTERVAL;
    NeighborCacheEntry *NCE;
    NeighborCacheEntry *NextNCE;
    uint OldNCCount;
    uint CheckCount = 0;
    uint CountPA = InterlockedCompareExchange((PLONG)&VA->NextPhysicalAdapterIndex,0,0);
    uint *SupportsOID = NULL;
    uint i;
    NDIS_PACKET *Probe, *ProbeList = NULL;
    uint CountLinkedNow = 0;
    uint CountLinkedLast = 0;

    //
    // Refresh 802.11 Sib stats for any PA that supports OID_MSRC_QUERY_SIB_TABLE.