headers.h

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

#pragma warning(disable:4115) // named type definition in parentheses
#pragma warning(disable:4200) // zero-sized array in struct/union
#pragma warning(disable:4201) // nameless struct/union
#pragma warning(disable:4213) // cast on l-value
#pragma warning(disable:4214) // bit field types other than int

//
// MSRC compile time switches that alter behavior of the driver.
//
#define ENABLE_MB_RETRIES      FALSE    // gregos: rexmit MB msg if not acked. Needs more testing.
#define ENABLE_MSRC_SIB_OID    TRUE     // gregos: if FALSE revert to PktPair even over AthMSRC
#define VRR_IDLE_UNICAST_PROBE TRUE     // gregos: iff TRUE include last unicast idle probing
#define PXE_CTL_MSG_ONLY       TRUE     // gregos: iff TRUE exclude packets from PXE.
#define SET_ACTIVE_WEAK        TRUE     // gregos: enable weakened SetSelfActive(F) condition (C#=F)
#define IS_CANDIDATE_ERR_CHECK TRUE     // gregos: dbg aid: check IsCandidateNeighbor()==ExpectedVSet
#define DHT_QUERY_VSET_NEW     TRUE     // gregos: fix DHT_QUERY_VSET for new VSet structures
#define ISCAND_WRAPPED_NEW     TRUE     // gregos: causes IS_CANDIDATE_ERR_CHECK to fire less often
#define BROADCAST_SUPPORTED    TRUE     // gregos: whether broadcast (relay) support included

#define NDIS_MINIPORT_DRIVER
#define NDIS51_MINIPORT 1
#define NDIS_WDM 1
#define NDIS51
#undef NTDDI_VERSION
#define NTDDI_VERSION NTDDI_WINXP
#define VRR_DDK_BUILD
#include <ndis.h>
#include <ntddk.h>
#ifdef VRR_DDK_BUILD
#include <headers-ddk.h>
#else
#include <align.h>
#endif
#include <malloc.h>

#define VRRASSERT(_x_) if (!(_x_)) \
    if (VrrGlobal.KdBreakPointOnAssert) \
        ASSERTMSG("VRRVRRASSERT(break):",(_x_)); \
    else \
        KdPrint(("VRRVRRASSERT(noop): at file %s line %i\n",__FILE__,__LINE__));

typedef unsigned int    uint;
typedef struct ProtocolAdapter ProtocolAdapter;
typedef struct MiniportAdapter MiniportAdapter;
typedef struct NeighborCache NeighborCache;
typedef struct NeighborCacheEntry NeighborCacheEntry;
typedef struct PktPairParams PktPairParams; 
typedef struct WcettParams WcettParams;
typedef struct NodeTable NodeTable;
typedef struct NodeTableEntry NodeTableEntry;
typedef struct RouteTable RouteTable;
typedef struct RouteTableEntry RouteTableEntry;
typedef struct TearDownCache TearDownCache;
typedef struct TearDownCacheEntry TearDownCacheEntry;
typedef struct AddressList AddressList;
typedef struct ProbeList ProbeList;
typedef struct ProbeListEntry ProbeListEntry;
typedef struct ZeroList ZeroList;
typedef struct ZeroListEntry ZeroListEntry;
typedef struct PacketIndex PacketIndex;
typedef struct BroadcastList BroadcastList;

#include "types.h"
#include "ether.h"
#include "vrr.h"
#include "ntddvrr.h"
#include "sr.h"
#include "linkcache.h"
#include "maintbuf.h"
#include "route.h"
#include <ipexport.h>

//
// Multipliers to convert 100ns time unit. 
//
#define MICROSECOND (10)
#define MILLISECOND (1000 * MICROSECOND)
#define SECOND      (1000 * MILLISECOND)
#define MINUTE      (60 * SECOND)

#if ENABLE_MB_RETRIES
#define VRR_MB_TX_ATTEMPTS      3                        // Comprises initial attempt plus rexmits.
#define MAINTBUF_REXMIT_TIMEOUT (250 * MILLISECOND)
#define MAINTBUF_LINK_TIMEOUT   (VRR_MB_TX_ATTEMPTS * MAINTBUF_REXMIT_TIMEOUT)
#define MAINTBUF_IDLE_TIMEOUT   ((Time)24 * 60 * MINUTE) // original MCL
//#define MAINTBUF_MAX_QUEUE      20                       // P for Plenty...  
#define MAX_ACK_DELAY           (80 * MILLISECOND)
#else
// We retransmit an ack request after this interval.
// Must be <= MAINTBUF_LINK_TIMEOUT. Equal means no rexmits.
#define MAINTBUF_REXMIT_TIMEOUT (500 * MILLISECOND)  // original MCL.

// We think a link is broken if we do not receive an ack after this interval.
#define MAINTBUF_LINK_TIMEOUT   (500 * MILLISECOND)  // original MCL.

// We assume the link is working within this interval after an ack.
#define MAINTBUF_HOLDOFF_TIME   (250 * MILLISECOND)  // original MCL.

// We delete a Maintenance Buffer Node after one day of inactivity.
// TODO - This is very large while we collect measurements.
#define MAINTBUF_IDLE_TIMEOUT   ((Time)24 * 60 * MINUTE) // original MCL

// We limit the number of packets held in a Maintenance Buffer Node.
// This number should be large enough to hold "initial" packets
// sent when connections are starting up.
#define MAINTBUF_MAX_QUEUE      4

// We delay an Acknowledgement no longer than 80ms.
#define MAX_ACK_DELAY           (80 * MILLISECOND)
#endif

// if PACKET_POOL_SZ <= SEND_BUF_SZ, then bad things happen really fast
#define PACKET_POOL_SZ       500

//
// Default next call to a timeout handler, in absence of anything sooner.
//
#define MIN_NCE_TIMOUT_INTERVAL  (200 * MILLISECOND)
#define MIN_NTE_TIMOUT_INTERVAL  (200 * MILLISECOND)
#define MIN_RTE_TIMOUT_INTERVAL  (500 * MILLISECOND)
#define MIN_PLE_TIMOUT_INTERVAL  (200 * MILLISECOND)
#define ZLE_TIMEOUT_INTERVAL     (1000 * MILLISECOND)
#define MIN_PXE_TIMOUT_INTERVAL  (200 * MILLISECOND)
#define MAX_MSG_TIMOUT_INTERVAL  (100 * MILLISECOND)

//
// Parameters controlling link quality procedures.
// See wcett.c for more ETX and PacketPair parameters.
//
#define DEFAULT_WCETT_PROBE_PERIOD  HELLO_MAX_FREQUENCY   // Original MCL: (1 * SECOND)
#define DEFAULT_WCETT_LOSS_INTERVAL (6 * SECOND)          // Original MCL: (30 * SECOND)
#define DEFAULT_WCETT_ALPHA     5                         // Weighting for ETX exp. moving ave. (X10). Original=1
#define DEFAULT_WCETT_BROKEN    ((uint)(0.99 * 4096))     // Delete NCE if P(loss)>0.n [encodes (0.n * 4096)]. Org=4055.
#define DEFAULT_WCETT_PKTPAIR_PROBE_PERIOD (60 * SECOND)  // Original: (60 * SECOND)
#define DEFAULT_WCETT_PKTPAIR_MIN_OVER_PROBES 2           // Recalculate using min RTT after n samples. Original: 10.
#define PKT2_ALPHA              819                       // Encoded(0.n * 4096) : Exp weighted moving av calc.
#define PKT2_SCALING            4096                      // Scaling factor for encoding Pkt2 bandwidth.
#define ETX_ADMIT_MIN           ((uint)(0.05 * 4096))     // Pass ETX iff P(loss)<0.n [encoded as (0.n * 4096)].
#define DEFAULT_WCETT_INITIAL   (ETX_ADMIT_MIN - 1)       // Exceed ETX admit threshold as soon as may be. 
#define ETX_EVICT_MIN           ((uint)(DEFAULT_WCETT_BROKEN * 0.9)) // ETX eviction theshold.
#if ENABLE_MSRC_SIB_OID
#define RATE_ADMIT_DEFAULT      MBPS_TO_BPS(12)           // ETT: Admit NCE if measured bandwidth exceeds this (in bps).
//#define RATE_EVICT_DEFAULT      MBPS_TO_BPS(6)            // ETT: Evict NCE if measured bandwidth below this (in bps).
#define RATE_EVICT_DEFAULT      MBPS_TO_BPS(4)            // ETT: Evict NCE if measured bandwidth below this (in bps).
#else
#define RATE_ADMIT_DEFAULT      MBPS_TO_BPS(18)           // PktPair: Admit NCE if measured bandwidth exceeds this (in bps).
#define RATE_EVICT_DEFAULT      MBPS_TO_BPS(9)            // PktPair: Evict NCE if measured bandwidth below this (in bps).
#endif
#define RSSI_ADMIT_DEFAULT      2                         // Admit NCE if RSSI exceeds this (dB).
#define RSSI_EVICT_DEFAULT      1                         // Evict NCE if RSSI below this (dB).

#define SIB_OID_EWMA_ALPHA      (10)                      // Exp Weight Ave alpha for 802.11 Sib, encoded as alpha*100.

//
// Parameters controlling the hello protocol.
//
#define HELLO_MAX_FREQUENCY     ((Time)(889 * MILLISECOND)) 
#define HELLO_MIN_FREQUENCY     ((Time)(HELLO_MAX_FREQUENCY * 1.25)) // per ETX expectations of [0%,25%] jitter
#define HELLO_FREQUENCY         (TimeoutInterval(HelloMaxFrequency, HelloMinFrequency))  // aka "t".
#define HELLO_MEAN_FREQUENCY    (HELLO_MAX_FREQUENCY + ((HELLO_MIN_FREQUENCY - HELLO_MAX_FREQUENCY) /2))
#define HELLO_MAX_MISSED_HELLOS 6                          // aka "k". Have seen missed O(25) on loaded net. 
#define HELLO_LIFETIME          (HELLO_MEAN_FREQUENCY * HELLO_MAX_MISSED_HELLOS)   // aka "kt".
#define HELLO_FAIL_TIMEOUT      (HELLO_LIFETIME * 2)                               // aka "2kt".

//
// Parameters controlling tx delay (with jitter), to enable aggregation. 
//
#define FWD_DELAY               (TimeoutInterval(5 * MILLISECOND, 10 * MILLISECOND))
#define SR_DELAY                (TimeoutInterval(5 * MILLISECOND, 10 * MILLISECOND))
#define SETUP_DELAY             (TimeoutInterval(5 * MILLISECOND, 10 * MILLISECOND))
#define TDOWN_DELAY             (TimeoutInterval(5 * MILLISECOND, 10 * MILLISECOND))
#define PLE_INITIAL_TX_DELAY    (TimeoutInterval(1 * MILLISECOND, 5 * MILLISECOND))

//
// Sundry tx-related parameters.
//
#define LONG_RETIREMENT         (((Time)1 * (Time)60 * (Time)MINUTE)) // Debug: indicates Setup and TD activity.
#define TDOWN_CACHE_LIFETIME    (10 * SECOND)
#define TDOWN_MAX_HK_INTERVAL   (1 * SECOND)
#define RTE_RETIRED_TIMEOUT     (2 * TDOWN_CACHE_LIFETIME)            // Retirement period for RTE other than type V.
#define RTE_VSET_RETIREMENT     (LONG_RETIREMENT + (10 * SECOND))
#define RTE_RETIRE_IMMEDIATE    1 
#define PLE_REXMIT_TIMEOUT      (2000 * MILLISECOND)
#define PLE_MAX_BACKOFF_SHIFT   3                           // Ceiling on exp backoff for SR (PLE) rexmits. SIGCOMM07 we tried 5.
#define PLE_MAX_REXMITS         15                          // Evict VSet member after this many failed SR. SIGCOMM07 we tried 15.
#define IDLE_PROBE_TIMEOUT      (60 * SECOND)
#define MAX_SRCANTIROUTE_SIZE   5

//
// parameters for packet index.
//
#define PACKET_INDEX_LIFETIME     ((Time)(10000 * MILLISECOND)) 

#if BROADCAST_SUPPORTED
//
// parameters for broadcast list
//
#define MIN_BLE_TIMOUT_INTERVAL  (200 * MILLISECOND)
#define BC_MIN_JITTER            0                        // millisecs
#define BC_MAX_JITTER            0                        // millisecs
#define BC_JITTER                (TimeoutInterval(MS_TO_TIME(VA->BroadcastJitterMinMs), MS_TO_TIME(VA->BroadcastJitterMaxMs)))
#define BROADCAST_RELAY_ENABLED  (0)
#define BLE_FLAG_NEW             1
#define BLE_FLAG_DUP             2
#endif

//
// Sundry parameters.
//
#define VRR_MAX_HOPCOUNT          32                        // Drop packet if hopcount exceeds this.
#define DRIVER_LOAD_DELAY         HELLO_LIFETIME            // delay [dis|en]able cycle s.t. neighbours fail links.
#define JOINING_ON_HOLD           1
#define PARTITION_REPAIR_ENABLED  1
#define TIME_TO_MS(nsc)           (uint)((nsc) / MILLISECOND) // Time encoded in units of 100ns.
#define MS_TO_TIME(ms)            ((ms) * MILLISECOND)        // Time encoded in units of 100ns.
#define TIMEOUT_TO_MS(t)          ((0 == t) ? 0 : TIME_TO_MS((uint)(t - KeQueryInterruptTime())))
#define KDPADDR                   %02x-%02x-%02x-%02x-%02x-%02x
#define FORMATADDRESS(a)          (uchar)a[0], (uchar)a[1],(uchar)a[2],(uchar)a[3],(uchar)a[4],(uchar)a[5]
#define TIMESTAMP                 (TIME_TO_MS(KeQueryInterruptTime()))
#define MAX_ATHMSRC_PA            (2)                         // Limits #PA to which we fwd an AthMSRC command.
#define DEFAULT_TRACE_NOISE       (2)                         // Default noise level for VrrTrace()
#define TX_DROP_ALL               (0)                         // Default for VA->TxDropAllButHello;
#define TX_DROP_HELLO             (0)                         // Default for VA->TxDropAllHello;

//
// Resolve constants that involve decimal point at compile
// time to avoid emitting floating point operations.
//
static const unsigned int EtxAdmitMin = ETX_ADMIT_MIN;
static const unsigned int EtxEvictMin = ETX_EVICT_MIN;
static const unsigned int DefaultWcettBroken = DEFAULT_WCETT_BROKEN;
static const unsigned int DefaultWcettInitial = DEFAULT_WCETT_INITIAL;
static const Time HelloMaxFrequency = HELLO_MAX_FREQUENCY;
static const Time HelloMinFrequency = HELLO_MIN_FREQUENCY;
static const Time HelloFailTimeout = HELLO_FAIL_TIMEOUT;
static const Time HelloLifetime = HELLO_FAIL_TIMEOUT;
static const Time DriverLoadDelay = HELLO_FAIL_TIMEOUT;


//
// Functionality in sidebug.c.
//
#define VRR_POOL_TAG    'LCM'

#ifdef POOL_TAGGING

#ifdef ExAllocatePool
#undef ExAllocatePool
#endif

#define ExAllocatePool(type, size) ExAllocatePoolWithTag((type), (size), VRR_POOL_TAG)

#endif // POOL_TAGGING

#ifndef COUNTING_MALLOC
#define COUNTING_MALLOC DBG
#endif

#if COUNTING_MALLOC

#ifdef ExFreePool
#undef ExFreePool
#endif

#define ExAllocatePoolWithTag(type, size, tag)  CountingExAllocatePoolWithTag((type), (size), (tag), __FILE__, __LINE__)

#define ExFreePool(p) CountingExFreePool(p)

extern VOID *
CountingExAllocatePoolWithTag(
    IN POOL_TYPE        PoolType,
    IN ULONG            NumberOfBytes,
    IN ULONG            Tag,
    IN PCHAR            File,
    IN ULONG            Line);

extern VOID
CountingExFreePool(
    PVOID               p);

extern VOID
InitCountingMalloc(void);

extern VOID
DumpCountingMallocStats(void);

extern VOID
UnloadCountingMalloc(void);

#endif  // COUNTING_MALLOC

//
// Functionality in protocol.c.
//

//
// We can only use physical adapters that have a sufficiently large
// frame size that we can add our VRR header.
//
#define PROTOCOL_MIN_FRAME_SIZE 1500

//
// We start dropping packets when a transmit queue gets bigger than this.
//
#define PROTOCOL_MAX_QUEUE      50

struct ProtocolAdapter {               // PA:
    MiniportAdapter *VirtualAdapter;

    uint Index;
    GUID Guid;

    NDIS_HANDLE Handle;

    //
    // List of physical adapters bound to the virtual adapter,
    // locked by VirtualAdapter->Lock.
    //
    struct ProtocolAdapter **Prev, *Next;

    //
    // For allocating packets in ProtocolReceive.
    //
    NDIS_HANDLE PacketPool;
    NDIS_HANDLE BufferPool;

    //
    // For calling NdisOpenAdapter and NdisCloseAdapter.
    //
    KEVENT Event;
    NDIS_STATUS Status;

    //
    // Synchronizes Channel & Bandwidth attribute retrieval from NDIS.
    //
    FAST_MUTEX Mutex;

    //
    // Various attributes of the adapter.
    //
    uint MaxFrameSize;
    PhysicalAddress Address;
    boolint Promiscuous;
    boolint ReceiveOnly;
    uint Channel;
    boolint ChannelConfigured;    // Was Channel manually configured?
    uint Bandwidth;
    boolint BandwidthConfigured;  // Was Bandwidth manually configured?
    boolint SupportsQuerySibTable;

    //
    // Cache for 802.11 STA info.
    //
    KSPIN_LOCK SibInfoLock;
    MSRCSibTableInfo SibInfo;

    //
    // Counters for monitoring/debugging purposes.
    //
    uint PacketsSent;           // Total calls to NdisSend.
    uint PacketsReceived;       // Total ProtocolReceive/ProtocolReceivePacket.
    uint PacketsReceivedTD;     // ProtocolReceive with Transfer Data.
    uint PacketsReceivedFlat;   // ProtocolReceive without Transfer Data.

    uint CountPacketPoolFailure;

    uint CountRecvOutstanding;  // Packets received but not completed.
    uint MaxRecvOutstanding;    // CountRecvOutstanding high-water mark.
    uint CountSentOutstanding;  // Packets sent but not completed.
    uint MaxSentOutstanding;    // CountSentOutstanding high-water mark.
};

extern ProtocolAdapter *
FindPhysicalAdapterFromIndex(MiniportAdapter *VA, uint Index);

extern ProtocolAdapter *
FindFirstPhysicalAdapter(MiniportAdapter *VA, VRRIf *Index);

extern ProtocolAdapter *
FindPhysicalAdapterFromGuid(MiniportAdapter *VA, const GUID *Guid);

extern boolint
ProtocolQueueFull(MiniportAdapter *VA, VRRIf OutIf);

extern NDIS_STATUS
ProtocolInit(const WCHAR *Name, MiniportAdapter *VA);

extern void
ProtocolCleanup(MiniportAdapter *VA);

extern void
ProtocolTransmit(ProtocolAdapter *PA, NDIS_PACKET *Packet);

extern void
ProtocolResetStatistics(ProtocolAdapter *PA);

typedef struct ProtocolRequest {
    NDIS_REQUEST Request;
    KEVENT Event;
    NDIS_STATUS Status;
    uint ContextOnStack;
    ProtocolAdapter *PA;
    MSRCSibTableInfo *Buffer;
} ProtocolRequest;

extern NDIS_STATUS
ProtocolRequestHelper(
    ProtocolAdapter *PA,
    NDIS_REQUEST_TYPE RT,   // Type of request to be done (Set or Query).
    NDIS_OID OID,           // Value to be set/queried.
    void *Info,             // Pointer to the buffer to be passed.
    uint Length,            // Length of data in above buffer.
    uint *Needed);          // Location to fill in with bytes needed in buffer.

extern void
ProtocolQuery(ProtocolAdapter *PA, VRR_INFO_PHYSICAL_ADAPTER *Info);

extern NTSTATUS
ProtocolControl(ProtocolAdapter *PA, VRR_CONTROL_PHYSICAL_ADAPTER *Control);

//
// Functionality in neighbor.c.
//

//
// The NeighborCacheEntry maps a virtual address and
// an interface index (representing another node's interface)
// to a physical address (of that other interface).
//
struct NeighborCacheEntry {     // NCE:
    NeighborCacheEntry *Next;
    NeighborCacheEntry *Prev;
    
    uint RefCnt;                // Reference counting on struct NCE.
   
    VirtualAddress VAddress;    // Cache VAddress: saves locks chasing *NTE.
    VRRIf RemIF;                // IFid of the neighbor's adapter as seen by neighbor.
    PhysicalAddress PAddress;   // Neighbour's layer 2 MAC address.