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

//
// Maintains list of broadcast packets received and potentially awaiting tx iff acting as a relay.
//

#include "headers.h"

//* BroadcastListInit
//
//  Initialize Broadcast list.
//
void
BroadcastListInit(BroadcastList *BL)
{
    KeInitializeSpinLock(&BL->Lock);
    BL->FirstBLE = BL->LastBLE = SentinelBLE(BL);
}

//* AddRefBLE
void
AddRefBLE(BroadcastListEntry *BLE)
{
    InterlockedIncrement(&BLE->RefCnt);
}

//* ReleaseBLE
void
ReleaseBLE(BroadcastListEntry *BLE)
{
    if (InterlockedDecrement(&BLE->RefCnt) == 0) {
        if (BLE->Buffer != NULL)
            ExFreePool(BLE->Buffer);
        ExFreePool(BLE);
    }
}

//* RemoveBLE
//
//  Caller must hold BL->Lock.
//
void
RemoveBLE(
    BroadcastList *BL,
    BroadcastListEntry *BLE)
{
    //
    // Sanity checks.
    //
    VRRASSERT(BLE != (BroadcastListEntry *)BL);

    //
    // Adjust pointers and free memory.
    //
    BLE->Next->Prev = BLE->Prev;
    BLE->Prev->Next = BLE->Next;
    ReleaseBLE(BLE);
    ReleaseBLE(BLE);
}

//* InsertBLE
//
//  Insert BLE into Broadcast List.
//
//  Caller must hold the BL->Lock.
//
void
InsertBLE(
    MiniportAdapter *VA,
    BroadcastListEntry *BLE)
{
    BroadcastList *BL = &VA->BL;
    BroadcastListEntry *NextBLE;
    uint RemoveNext = FALSE;

    VRRASSERT(BL != NULL);
    VRRASSERT(BLE != NULL);

    //
    // Find insertion point for the BLE in the list.
    //
    for (NextBLE = BL->FirstBLE; 
         NextBLE != SentinelBLE(BL);
         NextBLE = NextBLE->Next) {

         if (VirtualAddressLessThan(BLE->Origin,NextBLE->Origin))
             continue;
         if (VirtualAddressGreaterThan(BLE->Origin,NextBLE->Origin))
             break;
         if (BLE->FrameSeqNo < NextBLE->FrameSeqNo)
             continue;
         if (BLE->FrameSeqNo > NextBLE->FrameSeqNo)
             break;
         if (BLE->Timeout > NextBLE->Timeout)
             continue;
    }

    //
    // Insert the new BLE immediately prior to NextBLE.
    //
    BLE->Prev = NextBLE->Prev;
    BLE->Prev->Next = BLE;
    BLE->Next = NextBLE;
    BLE->Next->Prev = BLE;
    AddRefBLE(BLE);
    AddRefBLE(BLE);

    if (RemoveNext == TRUE)
        RemoveBLE(BL,NextBLE);
   
}

//* CreateBLE
//
//  Allocate a new Broadcast List entry.
//
BroadcastListEntry *
CreateBLE(
    VirtualAddress Origin,
    uint FrameSeqNo)
{
    BroadcastListEntry *BLE;

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

    //
    // Initialize the BLE.
    //
    RtlZeroMemory(BLE, sizeof *BLE);
    RtlCopyMemory(BLE->Origin,Origin,sizeof(VirtualAddress));
    BLE->FrameSeqNo = FrameSeqNo;

    return BLE;
}

//* FindBLE
//
//  Returns BLE iff in Broadcast List, else NULL.
//
//  Caller must hold the BL->Lock.
//
BroadcastListEntry *
FindBLE(
    BroadcastList *BL,
    VirtualAddress Origin,
    uint FrameSeqNo)
{
    BroadcastListEntry *BLE;

    VRRASSERT(BL != NULL);

    for (BLE = BL->FirstBLE; 
         BLE != SentinelBLE(BL);
         BLE = BLE->Next) {
         
        if (VirtualAddressEqual(BLE->Origin, Origin))
        if (FrameSeqNo == BLE->FrameSeqNo)
            return BLE;
    }

    return NULL;    
}

//* IsBroadcastRelay
//
//  Returns TRUE iff acting as relay for broadcast packets.
//
uint 
IsBroadcastRelay(
    MiniportAdapter *VA)
{
    return InterlockedCompareExchange(&VA->BroadcastRelay,FALSE,FALSE);
}

//* BroadcastListCleanup
//
// Flush the Broadcast list.
//
void
BroadcastListCleanup(
    MiniportAdapter *VA)
{
    BroadcastListEntry *BLE;
    BroadcastList *BL = &VA->BL;
    KIRQL OldIrql;

    KeAcquireSpinLock(&VA->BL.Lock, &OldIrql);
    while ((BLE = BL->FirstBLE) != SentinelBLE(BL))
        RemoveBLE(BL, BLE);
    KeReleaseSpinLock(&VA->BL.Lock, OldIrql);
}

//* BroadcastPacketComplete
//
//  Completion handler after sending a broadcast packet.
//  Cleans up the SRP packet from which NDIS packets were cloned.
//
void
BroadcastPacketComplete(
    MiniportAdapter *VA,
    SRPacket *srp,
    NDIS_STATUS Status)
{
    UNREFERENCED_PARAMETER(VA);
    UNREFERENCED_PARAMETER(Status);

    SRPacketFree(srp);
}


//* BroadcastOnEachAdapter
//
//  Sends a packet via every physical adapter simultaneously.
//  The operation completes when the last underlying transmit completes.
//  The operation completes successfully only if every
//  underlying transmit is successful.
//
void
BroadcastOnEachAdapter(
    MiniportAdapter *VA,
    SRPacket *srp,
    char *Buffer,
    uint BufferLen)
{
    ProtocolAdapter *PA;
    NDIS_PACKET *PacketList = NULL;
    NDIS_PACKET *Packet;
    NDIS_STATUS Status;
    KIRQL OldIrql;
    uint HeaderLength = SROptionListLength((InternalOption *)srp->VrrHello);

    //
    // We start with one reference (our own) for the SRPacket.
    //
    srp->ForwardCount = 1;
    srp->ForwardStatus = NDIS_STATUS_SUCCESS;

    //
    // First we build a temporary list of packet structures
    // and corresponding physical adapters. While doing this,
    // we also initialize the transmission count.
    // It starts with one, for our own reference for OrigPacket.
    //
    KeAcquireSpinLock(&VA->Lock, &OldIrql);
    for (PA = VA->PhysicalAdapters;
         PA != NULL;
         PA = PA->Next) {

        void *Data;
        EtherHeader *Ether;
        VRRHeader *VRR;
        char* pPayload;
        InternalOption *IntOpt;

        //
        // Unpack SRPacket into NDIS packet for transmission.
        // Do this manually: we hold VA->Lock which prevents
        // us using the normal tx path through FindNextHop.
        //
        Status = MiniportMakeEmptyPacket(VA,
                        sizeof(EtherHeader) + sizeof(VRRHeader) + HeaderLength + BufferLen,
                        &Packet, &Data);

        if (Status != NDIS_STATUS_SUCCESS) {
            KdPrint(("VrrBroadcast: MiniportMakeEmptyPacket() -> %8x\n",Status));
            continue;
        }

        //
        // Initialize ether header.
        //
        Ether = (EtherHeader *) Data;
        //RtlFillMemory(Ether->Dest, IEEE_802_ADDR_LENGTH, (uchar)0xff);
        RtlCopyMemory(Ether->Dest, srp->EtherDest, sizeof(VirtualAddress));
        Ether->Type = ETYPE_MSFT;

        //
        // Initialize VRR header.
        //
        VRR = (VRRHeader *) (Ether + 1);
        VRR->Code = VRR_CODE;
        RtlCopyMemory(VRR->IV, srp->IV, VRR_IV_LENGTH);
        VRR->HeaderLength = (ushort) HeaderLength;
        RtlCopyMemory(VRR->Source, VA->Address, sizeof(VirtualAddress));
        RtlFillMemory(VRR->Dest, sizeof(VirtualAddress), (uchar)0xff);
        RtlCopyMemory(VRR->Origin, srp->Origin, sizeof(VirtualAddress));
        VRR->FrameSeqNo = RtlUlongByteSwap(srp->FrameSeqNo);
        VRR->HopCount = srp->HopCount + 1;
        RtlCopyMemory(VRR->MAC, VA->CryptoKeyMAC, VRR_MAC_LENGTH);

        //
        // Initialize packet payload.
        //
        pPayload = (char *)(VRR + 1);
        if (BufferLen != 0)
            RtlCopyMemory(pPayload,Buffer,BufferLen);

        //
        // Remember the packet and corresponding physical adapter.
        // We temporarily use the OrigPacket field to build our list.
        //
        PC(Packet)->PA = PA;
        PC(Packet)->OrigPacket = PacketList;
        PacketList = Packet;
        srp->ForwardCount++;
    }
    KeReleaseSpinLock(&VA->Lock, OldIrql);

    //
    // Now we can transmit the packet via each physical adapter,
    // using the new packet structures.
    //
    while ((Packet = PacketList) != NULL) {
        PacketList = PC(Packet)->OrigPacket;
        PA = PC(Packet)->PA;

        //
        // Send the packet via a physical adapter.
        //
        PC(Packet)->srp = srp;
        PC(Packet)->TransmitComplete = VrrBroadcastComplete;
        ProtocolTransmit(PA, Packet);
    }

    //
    // Release our reference for the original packet.
    //
    if (InterlockedDecrement((PLONG)&srp->ForwardCount) == 0) {
        //
        // Complete the operation.
        //
        (*srp->TransmitComplete)(VA, srp, srp->ForwardStatus);
    }
}

//* BroadcastBLE
//
//  Creates a packet to send a broadcast.
//
static NDIS_STATUS
BroadcastBLE(
    MiniportAdapter *VA,
    BroadcastListEntry *BLE)
{
    SRPacket *SRP;
    NDIS_STATUS Status;
    KIRQL OldIrql;

    //
    // Initialize an SRPacket for the packet.
    //
    SRP = ExAllocatePool(NonPagedPool, sizeof *SRP);
    if (SRP == NULL) {
        return NDIS_STATUS_RESOURCES;
    }
    RtlZeroMemory(SRP, sizeof *SRP);

    //
    // Initialize the source & destination of this packet.
    //
    RtlCopyMemory(SRP->EtherDest, BLE->EthDest, sizeof(VirtualAddress));
    RtlCopyMemory(SRP->Source, VA->Address, sizeof(VirtualAddress));
    RtlCopyMemory(SRP->Dest, BLE->EthDest, sizeof(VirtualAddress));
    RtlCopyMemory(SRP->Origin, BLE->Origin, sizeof(VirtualAddress));
    SRP->FrameSeqNo = BLE->FrameSeqNo;
    SRP->HopCount = BLE->HopCount;
    SRP->TransmitComplete = VrrBroadcastSRPComplete;

    BroadcastOnEachAdapter(VA, SRP, BLE->Buffer, BLE->BufferLen);

    return NDIS_STATUS_SUCCESS;
}

//* UpdateBroadcastList
//
//  Update existing BLE or create a new one.
//
//  Returns TRUE iff a new BLE was created.
//
//  Caller must not hold BL->Lock.
//
uint
UpdateBroadcastList(
    MiniportAdapter *VA,
    VirtualAddress Origin,
    uint FrameSeqNo,
    uchar HopCount,
    VirtualAddress Source,
    VirtualAddress EthDest,
    uint Forward,
    uchar Buffer[],
    uint BufferLen)
{
    BroadcastList *BL = &VA->BL;
    BroadcastListEntry *BLE;
    uint NewBLE = FALSE;
    KIRQL OldIrql;
    Time Now = KeQueryInterruptTime();
    Time Timeout = 0;

    VRRASSERT(IsIEEEGroupAddress(EthDest));

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

    //
    // BLE have unique keys (Origin,FrameSeqNo).
    // Decide whether this is new or duplicate broadcast.
    //
    if (FindBLE(BL, Origin,FrameSeqNo) == NULL)
        NewBLE = TRUE;

    //
    // Update non-key fields within the BLE.
    //
    if ((BLE=CreateBLE(Origin,FrameSeqNo)) != NULL) {
        InsertBLE(VA, BLE);
        BLE->HopCount = HopCount;
        RtlCopyMemory(BLE->Source,Source,sizeof(VirtualAddress));
        RtlCopyMemory(BLE->EthDest,EthDest,sizeof(VirtualAddress));
        BLE->Timeout = Now + BLE_LIFETIME;
        BLE->Forward = Forward;
        BLE->Flags = (NewBLE) ? BLE_FLAG_NEW : BLE_FLAG_DUP;
        if (NewBLE == TRUE &&
            (BLE->Buffer = ExAllocatePool(NonPagedPool,BufferLen)) != NULL) {
            BLE->BufferLen = BufferLen;
            RtlCopyMemory(BLE->Buffer,Buffer,BufferLen);
        }
        if (NewBLE == TRUE && BLE->Forward == TRUE) {
            //
            // Avoid tripping over assert gt zero in reschedule timeout code.
            //
            Timeout = Now + BC_JITTER + (1 * MILLISECOND);
            BLE->TxTimeout = Timeout;

            //
            // Inline tx when MaxJitter==0 avoids inaccuracy in timeout scheduling.
            //
            if (VA->BroadcastJitterMaxMs == 0) {
                BroadcastBLE(VA,BLE);
                BLE->TxTimeout = 0;
            }
        }
    }

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

    if (Timeout != 0)
        MiniportRescheduleTimeout(VA,Now,Timeout);

    return NewBLE;
}

//* BroadcastListTimeout
//
//  Housekeeping of Broadcast List.
//
Time
BroadcastListTimeout(
    MiniportAdapter *VA,
    Time Now)
{
    NDIS_STATUS Status;
    LARGE_INTEGER Timestamp;
    LARGE_INTEGER Frequency;
    KIRQL OldIrql;
    Time NextTimeout = Now + MIN_BLE_TIMOUT_INTERVAL;
    BroadcastList *BL = &VA->BL;
    BroadcastListEntry *BLE;
    BroadcastListEntry *NextBLE;

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

    for (BLE = VA->BL.FirstBLE;
         BLE != SentinelBLE(&VA->BL);
         BLE = NextBLE) {

        Time BLETimeout = BLE->Timeout;

        NextBLE = BLE->Next;

        if (BLE->TxTimeout != 0 && BLE->TxTimeout < Now) {
            BroadcastBLE(VA,BLE);
            BLE->TxTimeout = 0;
        }

        if (BLETimeout < Now)
            RemoveBLE(BL,BLE);

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

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

    return NextTimeout;
}