node.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.
//

#include "headers.h"

#define VRR_MIN_NTE_REFCNT    2     // RefCnt of NTE in Node Table but otherwise unreferenced. 

//
// Type of function pointer for ordering an AddressList.
//
typedef uint pFuncAddressOrder(const VirtualAddress ax,const VirtualAddress ay,const VirtualAddress az);

//
// Type of function pointer yielding distance between a pair of VRR addresses.
//
typedef unsigned __int64 pFuncDistance(const VirtualAddress ax,const VirtualAddress ay);


//* Uint64ToVirtualAddress
//
void
Uint64ToVirtualAddress(unsigned __int64 u64, VirtualAddress Address)
{
    int i;

    for (i=sizeof(VirtualAddress)-1; i>=0; i--) {
        Address[i] = (uchar)(u64 & 0xff);
        u64 >>= 8;
    }
}

//* VirtualAddressToUint64
//
unsigned __int64
VirtualAddressToUint64(
    const VirtualAddress VAddr)
{
    unsigned __int64 u64 = 0;
    uint i;
    
    for (i=0; i < sizeof(VirtualAddress); i++) {
        u64 = u64 << 8;
        u64 += (uchar)VAddr[i];
    }
    
    return u64;
}

//* Uint64VirtualAddressDistance
//
//  Helper for VirtualAddressDistance and FNH.
//
//  Returns shortest distance between two unsigned __int64 in ring space. 
//
unsigned __int64
Uint64VirtualAddressDistance(
    unsigned __int64 x,
    unsigned __int64 y)
{
    if (x < y)
        return Uint64VirtualAddressDistance(y,x);

    if (x-y <= VRR_MAX_ADDR_DISTANCE)
        return x-y;
    else
        return (VRR_RINGSIZE - x) + y; 
}


//* VirtualAddressDistance
//
//  Return shortest distance between two Addresses in ring space. 
//
static unsigned __int64
VirtualAddressDistance(
    const VirtualAddress ax,
    const VirtualAddress ay)
{
    return Uint64VirtualAddressDistance(VirtualAddressToUint64(ax),
                                        VirtualAddressToUint64(ay));
}

//* VirtualAddressLessThan
//
uint
VirtualAddressLessThan(
    const VirtualAddress ax,
    const VirtualAddress ay)
{
    return VirtualAddressToUint64(ax) < VirtualAddressToUint64(ay);
}

//* VirtualAddressGreaterThan
//
uint
VirtualAddressGreaterThan(
    const VirtualAddress ax,
    const VirtualAddress ay)
{
    return VirtualAddressLessThan(ay,ax);
}

//* VirtualAddressLessThanOrEqualTo
//
uint
VirtualAddressLessThanOrEqualTo(
    const VirtualAddress ax,
    const VirtualAddress ay)
{
    return (VirtualAddressEqual(ax,ay) || VirtualAddressLessThan(ax,ay));
}

//* VirtualAddressGreaterThanOrEqualTo
//
uint
VirtualAddressGreaterThanOrEqualTo(
    const VirtualAddress ax,
    const VirtualAddress ay)
{
    return (VirtualAddressEqual(ax,ay) || VirtualAddressGreaterThan(ax,ay));
}

//* Uint64VirtualAddressIsToTheRight
//
//  See VirtualAddressIsToTheRight.
//
boolint
Uint64VirtualAddressIsToTheRight(
    unsigned __int64 x,
    unsigned __int64 y)
{
    if (x == y)
        return TRUE;  // arbitrary, but safe.
        
    if (x > y)
        return (x - y) > VRR_MAX_ADDR_DISTANCE;
    else
        return ! Uint64VirtualAddressIsToTheRight(y,x);
}

//* VirtualAddressIsToTheRight
//
// Given (ax,ay) returns TRUE iff ax should think ay to the right.
//
// Whether right is right or right is left depends on
// whether you're facing into the ring or out of the ring.
// It only matters that everyone is facing the same way. :-)
//
// Think of yourself standing at 3 o'clock facing out...
//
static boolint
VirtualAddressIsToTheRight(
    const VirtualAddress ax,
    const VirtualAddress ay)
{
    if (VirtualAddressEqual(ax,ay))
        return TRUE;  // arbitrary, but safe.
        
    if (VirtualAddressGreaterThan(ax,ay))
        return (VirtualAddressToUint64(ax) - VirtualAddressToUint64(ay)) > VRR_MAX_ADDR_DISTANCE;
    else
        return ! VirtualAddressIsToTheRight(ay,ax);
}

//* VirtualAddressIsCloser
//
// Given (ax,ay,az) returns TRUE iff (ax,az) are closer than (ay,az).
//
boolint
VirtualAddressIsCloser(
    const VirtualAddress ax,
    const VirtualAddress ay,
    const VirtualAddress az)
{
    return (VirtualAddressDistance(ax,az) < VirtualAddressDistance(ay,az));
}

//* Uint64DistanceRight
//
// Given (ax,ay) returns distance of ay from RHS of ax.
//
unsigned __int64
Uint64DistanceRight(
    unsigned __int64 x,
    unsigned __int64 y)
{
    unsigned __int64 ShortestDistance;
    
    ShortestDistance = Uint64VirtualAddressDistance(x, y);
    
    if (Uint64VirtualAddressIsToTheRight(x,y))
        // ay is closest to the RHS of ax.
        // Distance right is shortest distance.
        return Uint64VirtualAddressDistance(x, y);
    else
        return VRR_RINGSIZE - ShortestDistance;
        
}

//* DistanceRight
//
// Given (ax,ay) returns distance of ay from RHS of ax.
//
static __inline unsigned __int64
DistanceRight(
    const VirtualAddress ax,
    const VirtualAddress ay)
{
    unsigned __int64 x = VirtualAddressToUint64(ax);
    unsigned __int64 y = VirtualAddressToUint64(ay);
    unsigned __int64 ShortestDistance;
    
    ShortestDistance = VirtualAddressDistance(ax, ay);
    
    if (VirtualAddressIsToTheRight(ax,ay))
        // ay is closest to the RHS of ax.
        // Distance right is shortest distance.
        return VirtualAddressDistance(ax, ay);
    else
        return VRR_RINGSIZE - ShortestDistance;
        
}

//* Uint64DistanceLeft
//
// Given (ax,ay) returns distance of ay from LHS of ax.
//
unsigned __int64
Uint64DistanceLeft(
    unsigned __int64 x,
    unsigned __int64 y)
{
    return VRR_RINGSIZE - Uint64DistanceRight(x,y);
}

//* DistanceLeft
//
// Given (ax,ay) returns distance of ay from LHS of ax.
//
__inline unsigned __int64
DistanceLeft(
    const VirtualAddress ax,
    const VirtualAddress ay)
{
    return VRR_RINGSIZE - DistanceRight(ax,ay);
}

//* IsCloserRight
//
// Given (ax,ay,az) returns TRUE iff ax closer to RHS of az than is ay.
//
uint
IsCloserRight(
    const VirtualAddress ax,
    const VirtualAddress ay,
    const VirtualAddress az)
{
    return (DistanceRight(az,ax) < DistanceRight(az,ay));
}

//* IsCloserLeft
//
// Given (ax,ay,az) returns TRUE iff ax closer to LHS of az than is ay.
//
boolint
IsCloserLeft(
    const VirtualAddress ax,
    const VirtualAddress ay,
    const VirtualAddress az)
{
    return (DistanceLeft(az,ax) < DistanceLeft(az,ay));
}

//* VirtualAddressIsBetween
//
//  Given addresses (left,this,right) returns TRUE iff
//  left<=this<=right in the virtual address space.
//
//  (Sounds like a tautology...)
//  Implements C# "public bool IsBetween(NodeId left, NodeId right)"
//
static uint
VirtualAddressIsBetween(
    const VirtualAddress Left,
    const VirtualAddress Mid,
    const VirtualAddress Right)
{
    uint Result;

    //return (DistanceRight(Left,Mid) <= DistanceRight(Left,Right));
    if (VirtualAddressEqual(Left,Right)) {
        // Left == Mid == Right
        Result = VirtualAddressEqual(Left,Mid);
    }
    else if (VirtualAddressLessThanOrEqualTo(Left,Right)) {
        // Left <= Mid <= Right
        if (VirtualAddressLessThanOrEqualTo(Left,Mid) && 
            VirtualAddressLessThanOrEqualTo(Mid,Right))
            Result = TRUE;
        else
            Result = FALSE;
    }
    else {
        // Left > Right (wrapping)
        if (VirtualAddressLessThanOrEqualTo(Left,Mid) ||
            VirtualAddressGreaterThanOrEqualTo(Right,Mid))
            // Left <= Mid OR Right >= Mid
            Result = TRUE;
        else
            Result = FALSE;
    }
    return Result;
}

//* AddressListLast
//
//  Returns last element of an address list.
//
AddressList *
AddressListLast(AddressList *List)
{
    for (; List != NULL; List = List->Next)
        if (List->Next == NULL)
            return List;

    return NULL;
}

//* AddressListCount
//
//  Returns number of elements in linked list.
//
uchar
AddressListCount(AddressList *List)
{
    uchar Count;

    for (Count = 0; List != NULL; List = List->Next)
        Count++;

    return Count;
}

//* AddressListFind
//
//  Returns pointer to element matching given address or NULL iff
//  no such element is found.
//
static AddressList *
AddressListFind(AddressList *List, VirtualAddress Address)
{
    for (; List != NULL; List = List->Next)
        if (VirtualAddressEqual(Address, List->Address))
            return List;

    return NULL;
}

//* AddressListContains
//
//  Returns TRUE iff address appears in list.
//
uint
AddressListContains(AddressList *List, VirtualAddress Address)
{
    return (AddressListFind(List,Address) != NULL);
}

//* AddressListRemove
//
//  Remove an element from an address list.
//  No-op if address is not in the list.
//  Returns pointer to (new) head of list.
//
AddressList *
AddressListRemove(AddressList *List, VirtualAddress Address)
{
    AddressList *ALE;
    AddressList *Prior;

    if (List == NULL)
        return NULL;

    if (! AddressListContains(List,Address))
        return List;

    if (VirtualAddressEqual(List->Address, Address)) {
        ALE = List;
        List = List->Next;
        ExFreePool(ALE);
        return List;
    }

    Prior = List;
    for (ALE = List->Next; ALE != NULL; ALE = ALE->Next) {
        if (VirtualAddressEqual(Address, ALE->Address)) {
            Prior->Next = ALE->Next;
            ExFreePool(ALE);
            break;
        }
        Prior = ALE;
    }

    return List;
}

//* AddressListFree
//
//  Free memory held by address list.
//
void
AddressListFree(AddressList *List)
{
    AddressList *Next;

    while (List != NULL) {
        Next = List->Next;
        ExFreePool(List);
        List = Next;
    }
}

//* AddressListAddOrdered
//
//  Insert an address into an ordered list.
//  No-op if the address is already in the list.
//  Caller provides the ordering function.
//
//  Returns pointer to first element in the list.
//
AddressList *
AddressListAddOrdered(AddressList *List, VirtualAddress Base, VirtualAddress Address, pFuncAddressOrder *pFuncOrder)
{
    AddressList *New;
    AddressList *ALE;
    AddressList *Prior;

    VRRASSERT(pFuncOrder != NULL);

    if (AddressListContains(List, Address))
        return List;

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

    RtlZeroMemory(New,sizeof(*New));
    RtlCopyMemory(New->Address,Address,sizeof(VirtualAddress));

    if (List == NULL)
        return New;