node.c

Vitual Ring Routing 管你知不知道

            Closest = AddressListFindClosest(Candidates,VA->Address);
            for (ALE=Candidates; ALE!=NULL && ALE!=Closest; ALE=ALE->Next)
                pc++;     // IndexOf(closest)

            //
            // ref C# "if (pc-1 >= 0)"
            //
            if (pc-1 >= 0)    // unsigned "pc!=0" ?
                OnMyLeft = AddressListGetByIndex(Candidates,pc-1);
            else
                OnMyLeft = AddressListLast(Candidates);

            if (! VirtualAddressIsBetween(OnMyLeft->Address,VA->Address,Closest->Address))
                pc++;

            //
            // ref VirtualNeighbours.cs 
            //     "When local node is placed at the extremes pick right extreme using neighbors"
            //     "This might be too restrictive but adding it to both sides is likely to cause"
            //     "wrapping too early."
            //
            if (pc == 0 || pc == AddressListCount(Candidates)) {

                if (NonEmptyIntersection(NT->VSetLeft,Candidates)) {
                    AddressList *Last = AddressListLast(Candidates);
                    AddressList *Self = NULL;

                    Self = AddressListAdd(Self,VA->Address);
                    Last->Next = Self;
                    Added = TRUE;
                    InsertRemoteRight = TRUE;
                }
                if (NonEmptyIntersection(NT->VSetRight,Candidates)) {
                    AddressList *Self = NULL;

                    Self = AddressListAdd(Self,VA->Address);
                    Self->Next = Candidates;
                    Candidates = Self;
                    Added = TRUE;
                    InsertRemoteLeft = TRUE;
                }
            }

            if (!Added) {
                AddressList *Self = NULL;
                Self = AddressListAdd(Self,VA->Address);
                if (pc == 0) {
                    Self->Next = Candidates;
                    Candidates = Self;
                    InsertRemoteLeft = TRUE;
                }
                else {
                    OnMyLeft = AddressListGetByIndex(Candidates,pc-1);
                    Self->Next = OnMyLeft->Next;
                    OnMyLeft->Next = Self;
                    if (AddressListFind(Self,Candidate) != NULL)
                        InsertRemoteLeft = TRUE;
                    else
                        InsertRemoteRight = TRUE;
                }
            }

#if ISCAND_WRAPPED_NEW  // gregos: C# trips ExpectedCandidateError() : antr proposed fix
            //
            // if inserting(n,RemoteLeft) &&
            //     insert(n,RemoteLeft) &&
            //     contains(RemoteRight,n->left) &&
            //     Count(RemoteRight) < FULL_WING
            // then insert(n,RemoteRight) // n.b. Furthest(Right) would be wrong
            //
            if (InsertRemoteLeft && !InsertRemoteRight) {
                AddressList *FirstLeft = NULL;
                AddressList *CandidateInList = NULL;
                AddressList *RemoteRight = NULL;

                for (FirstLeft=Candidates; FirstLeft != NULL; FirstLeft=FirstLeft->Next)
                    if (FirstLeft->Next != NULL && VirtualAddressEqual(Candidate,FirstLeft->Next->Address))
                        break;

                VRRASSERT(FirstLeft != NULL);
                VRRASSERT(FirstLeft->Next != NULL);
                CandidateInList = AddressListFind(Candidates,Candidate);
                RemoteRight = CandidateInList->Next;

                if (AddressListCount(RemoteRight) < VRR_WING_SIZE + 1) {
                    AddressList *LeftOfSelf = NULL;
  
                    for (ALE=Candidates; ALE != NULL && LeftOfSelf == NULL; ALE=ALE->Next)
                        if (ALE->Next != NULL && VirtualAddressEqual(VA->Address,ALE->Next->Address))
                            LeftOfSelf = ALE;
                    if (LeftOfSelf != NULL && 
                        AddressListContains(RemoteRight,LeftOfSelf->Address)) {
                        CandidateInList->Next = AddressListAddOrdered(CandidateInList->Next,Candidate,VA->Address,IsCloserRight);
                    }
                }
            }

            //
            // if inserting(n,RemoteRight) &&
            //     insert(n,RemoteRight) &&
            //     contains(RemoteLeft,n->right) &&
            //     Count(RemoteLeft) < FULL_WING
            // then insert(n,RemoteLeft) // n.b. Furthest(Left) would be wrong
            //
            if (InsertRemoteRight && !InsertRemoteLeft) {
                AddressList *RemoteRight = NULL;
                AddressList *RightOfSelf = NULL;
                uint ToDoLeft = FALSE;

                RemoteRight = AddressListFind(Candidates,Candidate);
                RightOfSelf = AddressListFind(RemoteRight,VA->Address)->Next;

                if (RightOfSelf != NULL &&
                    AddressListCount(Candidates) - AddressListCount(RemoteRight) < VRR_WING_SIZE) {

                    for (ALE=Candidates; ALE != NULL && ToDoLeft == FALSE; ALE=ALE->Next) {
                        if (VirtualAddressEqual(ALE->Address,Candidate))
                            break;
                        else if (VirtualAddressEqual(ALE->Address,RightOfSelf->Address))
                            ToDoLeft = TRUE;
                    }
                }

                if (ToDoLeft == TRUE)
                    Candidates = AddressListAddOrdered(Candidates,Candidate,VA->Address,IsCloserRight);

            }
#endif
        }

        //
        // ref VirtualNeighbours.cs 
        //     "return candidates;"
        //     "local node may appear in more than one position in candidates"
        //
        if (Candidates != NULL) {
            AddressList *LeftMostSelf;
            AddressList *RightMostSelf = NULL;

            //
            // Anything to right of left-most self is candidate for VSetRight.
            // Ref C# "AddNodeRight((NodeId) candidates[i], out rem);"
            //
            LeftMostSelf = AddressListFind(Candidates,VA->Address);
            if (LeftMostSelf != NULL &&
                AddressListContains(LeftMostSelf,Candidate)){
                Result |= AddNodeFilter(VA,Candidate,RHS);
            }

            //
            // Anything to left of right-most self is candidate for VSetLeft.
            // Ref C# "AddNodeLeft((NodeId) candidates[i], out rem);"
            //
            if (LeftMostSelf != NULL)
                RightMostSelf = AddressListFind(LeftMostSelf->Next,VA->Address);
            if (RightMostSelf == NULL)
                RightMostSelf = LeftMostSelf;
            if (RightMostSelf != NULL) {
                AddressList *List;
                for (List=Candidates; List != RightMostSelf && List != NULL; List=List->Next) {
                    if (VirtualAddressEqual(List->Address,Candidate)) {
                        Result |= AddNodeFilter(VA,Candidate,LHS);
                        break;
                    }
                }
            }
        }

        //
        // Do not signal a VSet update if we know closer
        // nodes than Candidate in VSet or Candidates.
        //
        // Ref C#: "// update this with source"
        //         "if (sourceAddedLeft && addSource)"
        //
        if (UpdatingVSet == TRUE) {
            if (CountKnownCloser(VA,Candidates,Candidate,FALSE) >= VRR_WING_SIZE)
                Result &= ~VRR_NTE_FLAG_LHS;
            if (CountKnownCloser(VA,Candidates,Candidate,TRUE) >= VRR_WING_SIZE)
                Result &= ~VRR_NTE_FLAG_RHS;
        }

    }

    if (AddWithWrapping && Result != VRR_NTE_FLAG_NULL) {
        Result |= AddNodeFilter(VA,Candidate,RHS);
        Result |= AddNodeFilter(VA,Candidate,LHS);
    }

#if IS_CANDIDATE_ERR_CHECK // verify via IsCandidateNeighborLocked() to verify 
#if DBG
    //
    // Powerful Debugging aid.
    // If the set of addresses is known then the VRR_COMMAND_INIT_EVSET
    // interface can be used to populate VA->ExpectedVSet with the final
    // state of the VSet. The code below will compare the result computed
    // above against the final state. Set a breakpoint in the code below
    // and change "ChangeMe" and maybe "VrrTraceNoiseLevel" for a chance
    // to step through the code with the same input args and state that
    // just went wrong, e.g. "??ChangeMe=1" in WinDbg.
    //
    if (ExpectedCandidateError(VA,Candidate,Result,Candidates)) {
        uint ChangeMe = 0;
        uint SaveNoiseLevel = VA->VrrTraceNoiseLevel;
        VA->VrrTraceNoiseLevel = 0;  // Set breakpoint here.
        VRRASSERT(FALSE);
        if (ChangeMe != 0)
            IsCandidateNeighborLocked(VA,Candidate,CountVSet,RemoteVSet,UpdatingVSet);
        VA->VrrTraceNoiseLevel = SaveNoiseLevel;
    }
#endif
#endif

    AddressListFree(Candidates);

    return Result;

}

//* IsCandidateNeighbor
//
//  Returns TRUE iff a node with the supplied address would
//  be admitted to our neighbor set.  
//
//  Caller must not hold the Node Table lock.
//
uchar
IsCandidateNeighbor(
    MiniportAdapter *VA,
    VirtualAddress Candidate,
    uint CountVSet,
    VirtualAddress RemoteVSet[])
{
    uchar Result = VRR_NTE_FLAG_NULL;
    KIRQL OldIrql;

    KeAcquireSpinLock(&VA->NT.Lock, &OldIrql);
 
    Result = IsCandidateNeighborLocked(VA,Candidate,CountVSet,RemoteVSet,FALSE);
    
    KeReleaseSpinLock(&VA->NT.Lock, OldIrql);
    
    return Result;

}

//* IsDirectedPLE
//
//  Helper for ProbeListTimeout.
//  Returns TRUE iff directed PLE towards self+1 or self-1.
//
static uint
IsDirectedPLE(ProbeListEntry *PLE)
{
    uint Directed = FALSE; 

    if (PLE->SRDirection == VRR_SR_DIRECT_LHS ||
        PLE->SRDirection == VRR_SR_DIRECT_RHS)
        Directed = TRUE;
    
    return Directed;
}

typedef struct ProbeListSRList {
    struct ProbeListSRList *Next;
    VirtualAddress Address;
    uint FrameSeqNo;
    uchar SRDirection;
    AddressList *SRcAntiRoute;
} ProbeListSRList;

typedef struct ProbeListEvictList {
    struct ProbeListEvictList *Next;
    NodeTableEntry *NTE;
} ProbeListEvictList;

// Forward declaration.
void RemoveNTE(
    MiniportAdapter *VA,
    NodeTableEntry *NTE);

//* ProbeListTimeout
//
//  Housekeeping of Probe List.
//
Time
ProbeListTimeout(
    MiniportAdapter *VA,
    Time Now)
{
    NDIS_STATUS Status;
    LARGE_INTEGER Timestamp;
    LARGE_INTEGER Frequency;
    KIRQL OldIrql;
    Time NextTimeout = Now + MIN_PLE_TIMOUT_INTERVAL;
    ProbeList *PL = &VA->PL;
    NodeTable *NT = &VA->NT;
    ProbeListEntry *PLE;
    ProbeListEntry *NextPLE;
    ProbeListSRList *SRList = NULL;
    ProbeListEvictList *EvictList = NULL;
    uint AttemptingToJoin = FALSE;
    uint Evictions = FALSE;
    uint SnapPLECount = 0;
    uint ProbeLeftWing = FALSE;
    uint ProbeRightWing = FALSE;
    uint DirectedProbeFail = FALSE;
    uint SnapVSetIsComplete;

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

    //
    // Trim all but nearest PLE from probe list. 
    //
    TrimProbeList(VA);

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

    for (PLE = VA->PL.FirstPLE;
         PLE != SentinelPLE(&VA->PL);
         PLE = NextPLE) {

        Time PLETimeout = PLE->Timeout;

        NextPLE = PLE->Next;

        //
        // Only probe addresses that are within bounds of current VSet.
        //
        if (VSetCouldBeIn(VA,PLE->Address) == FALSE) {
            PLETimeout = Now;
            PLE->RexmitCount = PLE_MAX_REXMITS + 1;
        }

        //
        // Check for timeout of this PLE.
        //
        if (PLETimeout != 0 && PLETimeout <= Now) {
            PLE->RexmitCount++;
            if (PLE->RexmitCount > PLE_MAX_REXMITS) {
                //
                // Max rexmits exceeded. Remove the PLE.
                //
                NodeTableEntry *NTE;
                VrrTrace(VA,3,"PLETimeout: abandon probing PLE(s)",PLE->Address,NULL,NULL,NULL,0,NULL,0);

                //
                // If the PLE represents a vset member,
                // then we evict it from our vset and
                // start probing for a replacement.
                //
                if (IsDirectedPLE(PLE)) {
                    DirectedProbeFail = TRUE;
                }
                else {
                    if (AddressListContains(NT->VSetLeft,PLE->Address))
                        ProbeLeftWing = TRUE;
                    if (AddressListContains(NT->VSetRight,PLE->Address))
                        ProbeRightWing = TRUE;
                }
                NT->VSetLeft = AddressListRemove(NT->VSetLeft,PLE->Address);
                NT->VSetRight = AddressListRemove(NT->VSetRight,PLE->Address);
                NT->CountLeft = AddressListCount(NT->VSetLeft);
                NT->CountRight = AddressListCount(NT->VSetRight);
                if ((NTE=FindNTE(&VA->NT,PLE->Address)) != NULL) {
                    ProbeListEvictList *Evict;
                    if (NTE == VA->NT.Self) {
                        RemovePLE(VA,PLE);
                        continue;
                    }
                    Evict = ExAllocatePool(NonPagedPool, sizeof *Evict);
                    if (Evict != NULL) {
                        AddRefNTE(NTE);
                        Evict->NTE = NTE;
                        Evict->Next = EvictList;
                        EvictList = Evict;
                        RemoveNTE(VA,NTE);
                    }
                }
                RemovePLE(VA,PLE);

            }
            else {
                //
                // Send another SetupRequest and restart timeout. 
                //
                ProbeListSRList *SRL;
                uint Backoff;
                
                if ((SRL=ExAllocatePool(NonPagedPool, sizeof *SRL)) != NULL) {
                    RtlZeroMemory(SRL,sizeof *SRL);
                    RtlCopyMemory(SRL->Address, PLE->Address, sizeof(VirtualAddress));
                    PLE->FrameSeqNo = InterlockedIncrement(&VrrGlobal.NextFrameSeqNo);
                    SRL->FrameSeqNo = PLE->FrameSeqNo;
                    SRL->SRDirection = PLE->SRDirection;
 
                    if (PLE->SRcAntiRoute != NULL)
                        SRL->SRcAntiRoute = AddressListClone(PLE->SRcAntiRoute);

                    SRL->Next = SRList;
                    SRList = SRL;
                }
                Backoff = min(PLE->RexmitCount,PLE_MAX_BACKOFF_SHIFT);
                PLE->Timeout = Now + ((Time)PLE_REXMIT_TIMEOUT << Backoff);
            }
        }

        if (PLETimeout > Now && PLETimeout < NextTimeout)
            NextTimeout = PLETimeout;
         
    }

    //
    // Schedule directed probes e.g. replacing lost VSet members.
    // Ref VirtualNeighbors.cs::RemoveFromProbing(NodeId n)
    //     "initiate more probes if the vset is not complete"
    //     note: PL.Count==0 implies "!sentLeft" and "!sentRight"
    //
    if (ProbeLeftWing == TRUE || 
        ProbeRightWing == TRUE ||
        (VA->PL.Count == 0 && VSetIsComplete(VA) == FALSE)) {

        if (NT->CountLeft < VRR_WING_SIZE &&
            FindPLE(&VA->PL,VA->AddressDec) == NULL &&
            (PLE=FindOrCreatePLE(VA,VA->AddressDec))!=NULL) {
            VrrTrace(VA,3,"NT:NT=Timeout,Probe(Self-1)",NULL,NULL,VA->AddressDec,NULL,0,NULL,0);
            InterlockedIncrement(&VA->CountGenSRleft);
            PLE->SRDirection = VRR_SR_DIRECT_LHS;
            PLE->SRcAntiRoute = AddressListAdd(NULL,VA->Address);
            if (PLE->Timeout < NextTimeout)
                NextTimeout = PLE->Timeout;
        }

        if (NT->CountRight < VRR_WING_SIZE &&
            FindPLE(&VA->PL,VA->AddressInc) == NULL &&
            (PLE=FindOrCreatePLE(VA,VA->AddressInc))!=NULL) {
            VrrTrace(VA,3,"NT:NT=Timeout,Probe(Self+1)",NULL,NULL,VA->AddressInc,NULL,0,NULL,0);
            InterlockedIncrement(&VA->CountGenSRright);
            PLE->SRDirection = VRR_SR_DIRECT_RHS;
            PLE->SRcAntiRoute = AddressListAdd(NULL,VA->Address);
            if (PLE->Timeout < NextTimeout)
                NextTimeout = PLE->Timeout;
        }
    }

    SnapPLECount = PL->Count;
    SnapVSetIsComplete = VSetIsComplete(VA);

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

    //
    // As a final resort we give up trying to join an existing ring
    // and unilaterally start a singleton ring of our own, leaving
    // it up to the partition repair protocol to merge rings if an
    // opportunity presents.
    //
    // Ref C# "all else failed: rejoin and go active."