node.c

Vitual Ring Routing 管你知不知道

        if (VirtualAddressEqual(PLE->Address,VA->AddressInc))
            continue;
        if (CountKnownCloser(VA,PLELeft,PLE->Address,FALSE) >= MaxCountLeft &&
            CountKnownCloser(VA,PLERight,PLE->Address,TRUE) >= MaxCountRight) {
            VrrTrace(VA,4,"NT:PL=TrimProbeList",PLE->Address,NULL,NULL,NULL,0,NULL,0);
            RemovePLE(VA,PLE);
        }
    }

    AddressListFree(PLELeft);
    AddressListFree(PLERight);

}

//* FindOrCreatePLE
//
//  Returns PLE if match found in Probe List, else
//  tries to create a suitable PLE.
//
//  A return value of NULL means failure.
//
//  Caller must hold the NT->Lock.
//
ProbeListEntry *
FindOrCreatePLE(
    MiniportAdapter *VA,
    VirtualAddress Address)
{
    ProbeList *PL = &VA->PL;
    ProbeListEntry *PLE;
        
    PLE = FindPLE(PL, Address);
    if (PLE == NULL)
    if ((PLE=CreatePLE(Address)) != NULL)
        InsertPLE(VA, PLE);

    return PLE;
}

//* FindAndDeletePLE
//
//  Deletes entry from Probe List if the entry exists.
//
//  Caller must hold the NT->Lock.
//
ProbeListEntry *
FindAndDeletePLE(
    MiniportAdapter *VA,
    VirtualAddress Address)
{
    ProbeListEntry *PLE;
    ProbeList *PL = &VA->PL;
        
    if ((PLE = FindPLE(PL, Address)) != NULL)
        RemovePLE(VA, PLE);
        
    return PLE;
}

//* ProbeListCleanup
//
// Flush the Probe List.
//
void
ProbeListCleanup(
    MiniportAdapter *VA)
{
    ProbeListEntry *PLE;
    ProbeList *PL = &VA->PL;
    KIRQL OldIrql;

    KeAcquireSpinLock(&VA->NT.Lock, &OldIrql);
    while ((PLE = PL->FirstPLE) != SentinelPLE(PL)) {
        PLE->Next->Prev = PLE->Prev;
        PLE->Prev->Next = PLE->Next;
        AddressListFree(PLE->SRcAntiRoute);
        ExFreePool(PLE);
    }
    KeReleaseSpinLock(&VA->NT.Lock, OldIrql);
}

//* VSetIsWrapped
//
//  Returns TRUE iff our local VSet is wrapped.
//
//  Caller must hold NT->Lock.
//
static uint
VSetIsWrapped(MiniportAdapter *VA)
{
    NodeTable *NT = &VA->NT;

    if (NT->VSetLeft == 0 || NT->VSetRight == 0)
        return TRUE;

    return AddressListContains(NT->VSetRight,AddressListLast(NT->VSetLeft)->Address);

}

//* VSetCouldBeIn
//
//  Returns TRUE if supplied address could be admitted to our
//  VSet i.e. is within address range of present VSet.
//
//  Ref C# "internal bool CouldBeIn(NodeId n)"
//
//  Caller must hold NT->Lock.
//
static uint
VSetCouldBeIn(
    MiniportAdapter *VA,
    VirtualAddress Address)
{
    NodeTable *NT = &VA->NT;

    if (NT->CountLeft < VRR_WING_SIZE ||
        NT->CountRight < VRR_WING_SIZE ||
        VSetIsWrapped(VA))
        return TRUE;

    if (VirtualAddressIsBetween(AddressListLast(NT->VSetLeft)->Address,
                                Address,
                                AddressListLast(NT->VSetRight)->Address))
        return TRUE;

    return FALSE;
}


//* VSetIsComplete
//
//  Returns TRUE iff VSet is complete.
//  Ref C# "internal bool IsComplete()"
//
//  Caller must hold NT->Lock.
//
uint
VSetIsComplete(MiniportAdapter *VA)
{
    NodeTable *NT = &VA->NT;

    if (NT->CountLeft == 0 && NT->CountRight == 0)
        //
        // ref C# "single node system."
        //
        return TRUE;

    if (NT->CountLeft > 0 && NT->CountRight > 0) {
        //
        // ref C# "normal case complete leaf set"
        //
        if (NT->CountLeft == VRR_WING_SIZE && NT->CountRight == VRR_WING_SIZE)
            return TRUE;

        //
        // ref C# "less than l/2 nodes in system ; leaf set is wrapped"
        //
        // Deviates from C# : explicitly test both sidesof VSet for wrapping.
        // Original C# Contains(R,Last(L)) permits e.g. {NULL,5,6,2,5}=Complete
        //
        if (AddressListContains(NT->VSetLeft,AddressListLast(NT->VSetRight)->Address)) // 珻#
        if (AddressListContains(NT->VSetRight,AddressListLast(NT->VSetLeft)->Address)) // C#
            return TRUE;
    }

    return FALSE;

}

//* ExpectedCandidateError
//
//  Helper for IsCandidateNeighborLocked.
//
//  Compare IsCandidateNeighborLocked result against ExpectedVSet
//  and count number of times it rejects an expected VSet member.
//
//  Caller must hold the Node Table lock.
//
uint
ExpectedCandidateError(
    MiniportAdapter *VA,
    VirtualAddress Candidate,
    uchar Result,
    AddressList *Candidates)
{
    uint DetectedError = FALSE;
    uint i;

#if ISCAND_WRAPPED_NEW  // gregos: do NOT weaken IsCand conditions with this included
#else
    //
    // Weakened conditions for reporting error to exclude cases where
    // the algorithm cannot determine the correct answer. These occur
    // during initialization of the ring, for example, and may result
    // in a VSet update being temporarily rejected. Such cases are
    // resolved when the originator retries and supplies a different
    // VSet of his own to the one that caused our error.
    //
    if (AddressListCount(Candidates) == 3 &&
        VirtualAddressEqual(Candidates->Address,AddressListLast(Candidates)->Address)) {
        VA->RejExpBypass[0]++;
        return FALSE;
    }
#endif

    //
    // If candidate is in ExpectedVSet then IsCandidateNeigborLocked
    // should always accept it on the expected wing. Otherwise it is
    // an error.
    //
    for (i = 0; i < VRR_MAX_VSET_SIZE; i++) {
        if (VirtualAddressEqual(Candidate,NullAddress))
            continue;
        if (VirtualAddressEqual(Candidate,VA->Address))
            continue;
        if (VirtualAddressEqual(Candidate,VA->ExpectedVSet[i])) {
            if (i < VRR_WING_SIZE && (Result & VRR_SR_DIRECT_LHS) == 0) {
                VA->AddErrorVSet[i]++;
                DetectedError = TRUE;
            }
            if (i > VRR_WING_SIZE && (Result & VRR_SR_DIRECT_RHS) == 0) {
                VA->AddErrorVSet[i]++;
                DetectedError = TRUE;
            }
        }
    }

    return DetectedError;
}

//* NonEmptyIntersection
//
//  Helper for IsCandidateNeighborLocked. 
//  Returns TRUE iff the intersection of two address lists is not empty.
//
static uint
NonEmptyIntersection(AddressList *ListA, AddressList *ListB)
{
    for (; ListA!=NULL; ListA=ListA->Next)
        if (AddressListContains(ListB,ListA->Address))
            return TRUE;

    return FALSE;
}

//* AddNodeFilter
//
//  Helper for IsCandidateNeighborLocked.
//
//  Filters out attempts to add an invalid node to one wing of our VSet,
//  i.e. validates and treats invalid requests as no-op.
//
//  Ref VirtualNeighbors.cs::AddNodeLeft
//  Ref VirtualNeighbors.cs::AddNodeRight
//
//  Returns flag indicating whether proposed VSet member does indeed
//  belong in the proposed side of our VSet. 
//
static uchar
AddNodeFilter(
    MiniportAdapter *VA,
    VirtualAddress Candidate,
    uint RightWing)
{
    NodeTable *NT = &VA->NT;
    AddressList **VSet = (RightWing) ? &NT->VSetRight : &NT->VSetLeft;
    uint *WingCount = (RightWing) ? &NT->CountRight : &NT->CountLeft;
    uchar Accept = (RightWing) ? VRR_NTE_FLAG_RHS : VRR_NTE_FLAG_LHS;
    uchar Reject = VRR_NTE_FLAG_NULL;
    uchar Result = VRR_NTE_FLAG_NULL;

    if (VirtualAddressEqual(VA->Address,Candidate))
        //
        // Equivalent to C# no-op.
        //
        Result = Reject;
    else if (AddressListContains(*VSet,Candidate))
        //
        // Delta from C# : our callers are responsible for initiating 
        // probing of potential vset members based on our return value.
        //
        Result = Accept;
    else if (*WingCount < VRR_WING_SIZE)
        //
        // Equivalent to C# ".Add(Add)"
        //
        Result = Accept;
    else if (RightWing == TRUE &&
             AddressListCount(*VSet) != 0 &&
             VirtualAddressIsBetween(VA->Address,Candidate,AddressListLast(*VSet)->Address))
        //
        // Equivalent to C# "right.Add(Add)"
        //
        Result = Accept;
    else if (RightWing == FALSE &&
             AddressListCount(*VSet) != 0 &&
             VirtualAddressIsBetween(AddressListLast(*VSet)->Address,Candidate,VA->Address))
        //
        // Equivalent to C# "left.Add(Add)"
        //
        Result = Accept;

    return Result;

}

//* IsCandidateNeighborLocked
//
//  This is the decision procedure called by routines that need to
//  know whether a given node fits within the scope of our VSet.
//
//  It indicates by return which side of self, if any, a given
//  address would be admitted to our virtual neighbor set. It is
//  called by routines responsible for updating the VSet and probe
//  lists, but does not itself update either of these structures.
//
//  The caller must supply non-empty VSet, e.g. received in message from 
//  some counterparty, which we use to prevent premature VSet wrapping 
//  i.e. to prevent our VSet stablizing with node(s) reproduced on both
//  wings when the counterparty's VSet suggests there are exist other
//  potential neighbors that we have yet to hear from (or probe) directly.
//
//  Algorithm and style directly adopted from VirtualNeighbors.cs::AddNode
//  so as to facilitate manual comparison between the two, with respect to
//  which the structures representing a VSet (NTE list, VSetLeft, VSetRight)
//  have been changed to enable this routine to be entirely sequential.
//
//  Caller must hold the Node Table lock.
//
static uchar
IsCandidateNeighborLocked(
    MiniportAdapter *VA,
    VirtualAddress Candidate,
    uint CountVSet,
    VirtualAddress RemoteVSet[],
    uint UpdatingVSet)
{
    NodeTable *NT = &VA->NT;
    NodeTableEntry *NTE;
    uchar Result = VRR_NTE_FLAG_NULL;
    uint IsWrappedLocal = VSetIsWrapped(VA);
    uint IsWrappedRemote = FALSE;
    uint ShouldWrap = FALSE;
    uint AddWithWrapping = FALSE;
    const uint RHS = TRUE;
    const uint LHS = FALSE;
    AddressList *Candidates = NULL;

    VRRASSERT(CountVSet != 0);
    VRRASSERT(CountVSet <= VRR_WING_SIZE + 1 + VRR_WING_SIZE);
    VRRASSERT(RemoteVSet != NULL);

    if (CountVSet == 0 || RemoteVSet == NULL)
        return VRR_NTE_FLAG_NULL;

    if (VA->VrrTraceNoiseLevel >= 3 ) {
        uint CountLocVSet = VA->NT.CountLeft+1+VA->NT.CountRight;
        VirtualAddress MyVSet[VRR_MAX_VSET_SIZE];
        VSetToFlatBuffer(VA,MyVSet);
        VrrTrace(VA,3,"gregos IsCand 0",Candidate,Candidate,Candidate,"CountLocVSet",CountLocVSet,"CountRemVSet",CountVSet);
        VrrTraceVSet(VA,"IsCand LocVSet", (CountLocVSet > 0) ? MyVSet[0] : NULL,
            (CountLocVSet > 1) ? MyVSet[1] : NULL, (CountLocVSet > 2) ? MyVSet[2] : NULL,
            (CountLocVSet > 3) ? MyVSet[3] : NULL, (CountLocVSet > 4) ? MyVSet[4] : NULL);
        VrrTraceVSet(VA,"IsCand RemVSet", (CountVSet > 0) ? RemoteVSet[0] : NULL,
            (CountVSet > 1) ? RemoteVSet[1] : NULL, (CountVSet > 2) ? RemoteVSet[2] : NULL,
            (CountVSet > 3) ? RemoteVSet[3] : NULL, (CountVSet > 4) ? RemoteVSet[4] : NULL);
    }

    //
    // Implements VirtualNeighbors.cs::IsWrapped(NodeId[] vset, NodeId source)
    //
    if (CountVSet == 1)
        IsWrappedRemote = TRUE;

    if (CountVSet > 1) {
        AddressList *List = AddressListFromArray(RemoteVSet,CountVSet);
        if (AddressListCount(List) < CountVSet)
            IsWrappedRemote = TRUE;
        AddressListFree(List);
    }

    //
    // Implements VirtualNeighbours.cs::ShouldWrap()
    //     "return (probing.Count < 2 && node.forwardingTable.NodeCount < Parameters.r) || !node.Initialized;"
    //
    if (VA->PL.Count < 2 && 
        (NT->CountLeft + NT->CountRight) < (VRR_WING_SIZE * 2))
        ShouldWrap = TRUE;

    if (IsDriverInitialized(VA) == FALSE)
        ShouldWrap = TRUE;

    //
    // Implements (read-only) VirtualNeighbours.cs::AddNode(...)
    //
    if (NT->CountLeft == 0 && NT->CountRight == 0 &&
        IsWrappedRemote && ShouldWrap) {
        AddWithWrapping = TRUE;
    }

    if (IsWrappedLocal)
        AddWithWrapping = TRUE;

    if (AddWithWrapping) {
        //
        // ref VirtualNeighbours.cs
        //     "handle case where the virtual neighbor set is wrapped"
        //
        Result |= AddNodeFilter(VA,Candidate,RHS);
        Result |= AddNodeFilter(VA,Candidate,LHS);
    }
    else if (CountVSet == 1) {
        //
        // ref VirtualNeighbours.cs
        //     "virtual neighbor set is not wrapped"
        //
        if ((NT->CountLeft + NT->CountRight) == (VRR_WING_SIZE * 2)) {
            Result |= AddNodeFilter(VA,Candidate,RHS);
            Result |= AddNodeFilter(VA,Candidate,LHS);
        }
        else if (DistanceRight(VA->Address,Candidate) < DistanceLeft(VA->Address,Candidate)) {
            Result |= AddNodeFilter(VA,Candidate,RHS);
        }
        else {
            Result |= AddNodeFilter(VA,Candidate,LHS);
        }
    }
    else {
        //
        // Implements VirtualNeighbours.cs::BuildCandidates(NodeId[] vset)
        // Ref VirtualNeighbours.cs
        //     "builds candidate list sorted left to right and with the local node added"
        //
        // Unusually for an AddressList, Candidates may contain duplicate
        // elements e.g. representing Self or other nodes in a remote, 
        // oversized VSet that may be wrapped.
        //
        uint i;
        
        if((Candidates=AddressListAdd(NULL,RemoteVSet[0]))!=NULL)
            for (i=1; i < CountVSet; i++)
                AddressListLast(Candidates)->Next = AddressListAdd(NULL,RemoteVSet[i]);

        //
        // ref VirtualNeighbours.cs
        //     "insert local node in list if not in"
        // i.e., where would we sit in Candidates' VSet.
        //
        if (! AddressListContains(Candidates,VA->Address)) {
            AddressList *Closest;
            AddressList *ALE;
            AddressList *OnMyLeft;
            int pc = 0;
            uint Added = FALSE;
            uint j;
            uint InsertRemoteLeft = FALSE;
            uint InsertRemoteRight = FALSE;