node.c

Vitual Ring Routing 管你知不知道

    if ((*pFuncOrder)(Address,List->Address,Base)) {
        New->Next = List;
        return New;
    }

    Prior = List;
    for (ALE = List->Next; ALE != NULL; ALE = ALE->Next) {
        if ((*pFuncOrder)(Address,ALE->Address,Base))
            break;
        Prior = ALE;
    }
    New->Next = Prior->Next;
    Prior->Next = New;

    return List;
}

//* AddressListAdd
//
//  Add an address to (head of) an address list.
//  No-op if the address is already in the list.
//
//  Returns pointer to first element in the list.
//
AddressList *
AddressListAdd(AddressList *List, VirtualAddress Address)
{
    AddressList *New;

    if (List != NULL && AddressListContains(List, Address))
        return List;

    if ((New=ExAllocatePool(NonPagedPool, sizeof *New)) == NULL)
        return List;

    RtlCopyMemory(New->Address,Address,sizeof(VirtualAddress));
    New->Next = List;

    return New;
}

//* AddressListClone
//
//  Make a clone of an AddressList, preserving
//  the ordering of the original.
//
//  Caller must call AddressListFree when done.
//  Returns pointer to first element in the clone.
//
AddressList *
AddressListClone(AddressList *Original)
{
    AddressList *Reverse = NULL;
    AddressList *Clone = NULL;
    AddressList *ALE;

    while (Original != NULL) {
        Reverse = AddressListAdd(Reverse, Original->Address);
        Original = Original->Next;
    }

    ALE = Reverse;
    while (ALE != NULL) {
        Clone = AddressListAdd(Clone, ALE->Address);
        ALE = ALE->Next;
    }

    AddressListFree(Reverse);

    return Clone;
}


//* AddressListToArray
//
//  Copies addresses from list to an array.
//  Caller must supply memory for the target array.
//
//  Returns number of elements copied.
//
uint
AddressListToArray(AddressList *List, VirtualAddress Array[], uint Count)
{
    uint i;

    if (Array == NULL)
        return 0;

    Count = min(Count,AddressListCount(List));

    for (i = 0; i < Count; i++) {
        RtlCopyMemory(&Array[i],List->Address,sizeof(VirtualAddress));
        List = List->Next;
    }

    return Count;
}

//* AddressListFromArray
//
//  Allocate and initialize an address list given an array of addresses.
//
//  Returns pointer to head of list.
//
AddressList *
AddressListFromArray(VirtualAddress Array[], uint ArraySize)
{
    AddressList *List = NULL;
    uint i;

    if (ArraySize == 0)
        return NULL;

    for (i = ArraySize; i > 0; i--) 
        List = AddressListAdd(List, Array[i-1]);

    return List;
}

//* AddressListTrim
//
//  Trim address list to a given size by removing elements from its tail.
//  Returns pointer to list, which may have become NULL.
//
AddressList *
AddressListTrim(AddressList *List, uint Limit)
{
    AddressList *ALE = List;
    uint Count;

    if (Limit == 0) {
        AddressListFree(List);
        return NULL;
    }

    for (Count = 0; ALE != NULL && Count < Limit-1; ALE = ALE->Next)
        Count++;

    if (ALE != NULL) {
        AddressListFree(ALE->Next);
        ALE->Next = NULL;
    }

    return List;
}

//* AddressListGetByIndex
//
//  Return pointer to n'th element of list if given
//  zero-based index is valid, otherwise NULL.
//
static AddressList *
AddressListGetByIndex(AddressList *List, uint Index)
{
    uint Limit = AddressListCount(List) - 1;
    uint i;

    if (Index > Limit)
        return NULL;

    for (i=0; i < Index; i++)
        List = List->Next;

    return List;
}

//* AddressListFindClosest
//
//  Returns pointer to element in address list that has
//  the closest address to a given address, or NULL if
//  address list is empty.
//
static AddressList *
AddressListFindClosest(AddressList *List, VirtualAddress Address)
{
    AddressList *Closest = List;
    AddressList *ALE;
    unsigned __int64 BestDistance;

    BestDistance=VirtualAddressDistance(Address,Closest->Address);
    for (ALE=List; ALE!=NULL; ALE=ALE->Next) {
         unsigned __int64 Distance;
         Distance = VirtualAddressDistance(Address,ALE->Address);
         if (Distance < BestDistance) {
             Closest = ALE;
             BestDistance = Distance;
        }
    }
    return Closest;
}

// PL:
//* CountKnownCloser
//
//  Helper for IsCandidateNeighborLocked.
//
//  Returns number of known addresses in supplied lists that
//  are closer to self than some given Candidate address.
//
//  Caller must hold the Node Table lock.
//
static uint
CountKnownCloser(
    MiniportAdapter *VA,
    AddressList *List,
    VirtualAddress Candidate,
    uint RightWing)
{
    AddressList *Union = NULL;
    AddressList *ALE;
    ProbeList *PL = &VA->PL;
    ProbeListEntry *PLE;
    uint CountCloser;
    AddressList *VSetWing = (RightWing) ? VA->NT.VSetRight : VA->NT.VSetLeft;
    pFuncDistance *pDistanceFunc = (RightWing) ? DistanceRight : DistanceLeft;

    //
    // Caller may want us to scan an arbitrary AddressList.
    //
    for (ALE=List; ALE != NULL; ALE = ALE->Next) {
        if (VirtualAddressEqual(VA->Address,ALE->Address) == FALSE &&
            (*pDistanceFunc)(VA->Address, ALE->Address) < (*pDistanceFunc)(VA->Address, Candidate))
            Union = AddressListAdd(Union,ALE->Address);
    }


    //
    // Scan VSetLeft or VSetRight list.
    //
    for (ALE=VSetWing; ALE != NULL; ALE = ALE->Next) {
        if ((*pDistanceFunc)(VA->Address, ALE->Address) < (*pDistanceFunc)(VA->Address, Candidate))
            Union = AddressListAdd(Union,ALE->Address);
    }

    CountCloser = AddressListCount(Union);

    AddressListFree(Union);

    return CountCloser;

}

//* ProbeListInit
void
ProbeListInit(ProbeList *PL)
{
    PL->FirstPLE = PL->LastPLE = SentinelPLE(PL);
}

//
// Forward declaration.
//
boolint UpdateVrrAPIJoined(MiniportAdapter *VA);

//* RemovePLE
void
RemovePLE(
    MiniportAdapter *VA,
    ProbeListEntry *PLE)
{
    ProbeList *PL = &VA->PL;
    //
    // Sanity checks.
    //
    VRRASSERT(PLE != (ProbeListEntry *)PL);

    //
    // Adjust pointers and free memory.
    //
    PLE->Next->Prev = PLE->Prev;
    PLE->Prev->Next = PLE->Next;
    AddressListFree(PLE->SRcAntiRoute);
    ExFreePool(PLE);

    PL->Count--;

    UpdateVrrAPIJoined(VA);
}

//* InsertPLE
//
//  Insert PLE into Probe List.
//
//  Caller must hold the NT->Lock.
//
void
InsertPLE(
    MiniportAdapter *VA,
    ProbeListEntry *PLE)
{
    ProbeList *PL = &VA->PL;
    ProbeListEntry *NextPLE;
    NodeTableEntry *Self = VA->NT.Self;

    VRRASSERT(PL != NULL);
    VRRASSERT(PLE != NULL);

    //
    // Find insertion point for new PLE in the Probe List.
    //
    for (NextPLE = PL->FirstPLE; 
         NextPLE != SentinelPLE(PL);
         NextPLE = NextPLE->Next) {
         
        if (DistanceRight(Self->Address,NextPLE->Address) < DistanceRight(Self->Address, PLE->Address))
            continue;
            
        if (DistanceRight(Self->Address,PLE->Address) < DistanceRight(Self->Address, NextPLE->Address))
            break;
        
        break;
    }

    //
    // Insert the new PLE immediately prior to NextPLE.
    //
    PLE->Prev = NextPLE->Prev;
    PLE->Prev->Next = PLE;
    PLE->Next = NextPLE;
    PLE->Next->Prev = PLE;

    PL->Count++;
   
}

//* CreatePLE
//
//  Allocate a new Probe List Entry in memory.
//
ProbeListEntry *
CreatePLE(
    VirtualAddress Address)
{
    ProbeListEntry *PLE;

    PLE = ExAllocatePool(NonPagedPool, sizeof *PLE);
    if (PLE == NULL)
        return NULL;

    //
    // Initialize the PLE.
    //
    RtlZeroMemory(PLE, sizeof *PLE);
    RtlCopyMemory(PLE->Address,Address,sizeof(VirtualAddress));
    PLE->Timeout = KeQueryInterruptTime() + PLE_INITIAL_TX_DELAY;
    PLE->SRDirection = NULL_SR_FLAGS;

    return PLE;
}

//* FindPLE
//
//  Returns PLE iff in Probe List, else NULL.
//
//  Caller must hold the NT->Lock.
//
ProbeListEntry *
FindPLE(
    ProbeList *PL,
    VirtualAddress Address)
{
    ProbeListEntry *PLE;

    VRRASSERT(PL != NULL);

    for (PLE = PL->FirstPLE; 
         PLE != SentinelPLE(PL);
         PLE = PLE->Next) {
         
        if (VirtualAddressEqual(PLE->Address, Address))
            return PLE;
    }

    return NULL;    
}

//* FindPLEFromFrameSeqNo
//
//  Returns PLE iff in Probe List, else NULL.
//
//  Caller must hold the NT->Lock.
//
ProbeListEntry *
FindPLEFromFrameSeqNo(
    ProbeList *PL,
    uint FrameSeqNo)
{
    ProbeListEntry *PLE;

    VRRASSERT(PL != NULL);

    for (PLE = PL->FirstPLE; 
         PLE != SentinelPLE(PL);
         PLE = PLE->Next) {
         
        if (PLE->FrameSeqNo == FrameSeqNo)
            return PLE;
    }

    return NULL;    
}


//* TrimProbeList
//
//  Trim the probe list to remove any entries that are not
//  within nearest known VRR_WING_SIZE nodes from self.
//
//  Caller must hold NT->Lock.
void
TrimProbeList (
    MiniportAdapter *VA)
{
    ProbeList *PL = &VA->PL;
    NodeTable *NT = &VA->NT;
    ProbeListEntry *PLE;
    ProbeListEntry *NextPLE;
    NodeTableEntry *NTE;
    NodeTableEntry *Self = VA->NT.Self;
    unsigned __int64 BoundRight = VRR_RINGSIZE;
    unsigned __int64 BoundLeft = VRR_RINGSIZE;
    uint i;
    AddressList *PLELeft = NULL;
    AddressList *PLERight = NULL;
    uint MaxCountLeft = VRR_WING_SIZE;
    uint MaxCountRight = VRR_WING_SIZE;

    if (VA->PL.FirstPLE == SentinelPLE(PL))
        return;

    //
    // Build ordered lists from PLE.
    //
    for (PLE = PL->FirstPLE; PLE != SentinelPLE(PL); PLE = PLE->Next) {
        PLERight = AddressListAddOrdered(PLERight,Self->Address,PLE->Address,IsCloserRight);
        PLELeft = AddressListAddOrdered(PLELeft,Self->Address,PLE->Address,IsCloserLeft);
    }

    //
    // AddressDec and AddressInc are special cases, if they are in use.
    // They are unlikely to respesent real nodes, but they might.
    //
    if (AddressListContains(PLERight,VA->AddressInc))
        MaxCountRight++;
    if (AddressListContains(PLELeft,VA->AddressDec))
        MaxCountLeft++;

    //
    // Remove PLE except for the closest to self.
    //
    for (PLE = PL->FirstPLE; PLE != SentinelPLE(PL); PLE = NextPLE) {
        NextPLE = PLE->Next;

        if (VirtualAddressEqual(PLE->Address,VA->Address))
            continue;
        if (VirtualAddressEqual(PLE->Address,VA->AddressDec))
            continue;