// -*- 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 short-lived summary of messages and/or packets recently seen.
//

#include "headers.h"

// PX:
//* PacketIndexInit
//
//  Initialize Packet Index.
//
void
PacketIndexInit(PacketIndex *PX)
{
    KeInitializeSpinLock(&PX->Lock);
    PX->FirstPXE = PX->LastPXE = SentinelPXE(PX);
}

//* AddRefPXE
void
AddRefPXE(PacketIndexEntry *PXE)
{
    InterlockedIncrement(&PXE->RefCnt);
}

//* ReleasePXE
void
ReleasePXE(PacketIndexEntry *PXE)
{
    if (InterlockedDecrement(&PXE->RefCnt) == 0) {
        ExFreePool(PXE);
    }
}

//* RemovePXE
//
//  Caller must hold PX->Lock.
//
void
RemovePXE(
    PacketIndex *PX,
    PacketIndexEntry *PXE)
{
    //
    // Sanity checks.
    //
    VRRASSERT(PXE != (PacketIndexEntry *)PX);

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

//* InsertPXE
//
//  Insert PXE into Packet Index.
//
//  Caller must hold the PX->Lock.
//
void
InsertPXE(
    MiniportAdapter *VA,
    PacketIndexEntry *PXE)
{
    PacketIndex *PX = &VA->PX;
    PacketIndexEntry *NextPXE;
    uint RemoveNext = FALSE;

    VRRASSERT(PX != NULL);
    VRRASSERT(PXE != NULL);

    //
    // Find insertion point for the PXE in the Packet Index.
    //
    for (NextPXE = PX->FirstPXE; 
         NextPXE != SentinelPXE(PX);
         NextPXE = NextPXE->Next) {

         if (VirtualAddressLessThan(PXE->Origin,NextPXE->Origin))
             continue;
         if (VirtualAddressGreaterThan(PXE->Origin,NextPXE->Origin))
             break;
         if (PXE->FrameSeqNo < NextPXE->FrameSeqNo)
             continue;
         if (PXE->FrameSeqNo > NextPXE->FrameSeqNo)
             break;
         //
         // Duplicate: replace older PXE in case new instance still in use.
         //
         RemoveNext = TRUE;
         break;
    }

    //
    // Insert the new PXE immediately prior to NextPXE.
    //
    PXE->Prev = NextPXE->Prev;
    PXE->Prev->Next = PXE;
    PXE->Next = NextPXE;
    PXE->Next->Prev = PXE;
    AddRefPXE(PXE);
    AddRefPXE(PXE);

    if (RemoveNext == TRUE)
        RemovePXE(PX,NextPXE);
   
}

//* CreatePXE
//
//  Allocate a new Packet Index Entry in memory.
//
PacketIndexEntry *
CreatePXE(
    VirtualAddress Origin,
    uint FrameSeqNo,
    uchar Type)
{
    PacketIndexEntry *PXE;

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

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

    return PXE;
}

//* FindPXE
//
//  Returns PXE iff in Packet Index, else NULL.
//
//  Caller must hold the PX->Lock.
//
PacketIndexEntry *
FindPXE(
    PacketIndex *PX,
    VirtualAddress Origin,
    uint FrameSeqNo,
    uchar Type)
{
    PacketIndexEntry *PXE;

    VRRASSERT(PX != NULL);

    for (PXE = PX->FirstPXE; 
         PXE != SentinelPXE(PX);
         PXE = PXE->Next) {
         
        if (IsUnspecified(Origin) || VirtualAddressEqual(PXE->Origin, Origin))
        if (FrameSeqNo == 0 || FrameSeqNo == PXE->FrameSeqNo)
        if (PXE->Type == Type)
            return PXE;
    }

    return NULL;    
}

//* UpdatePacketIndex
//
//  Update existing PXE or create a new one.
//
//  Returns TRUE iff a new PXE was created.
//
//  Caller must not hold PX->Lock.
//
uint
UpdatePacketIndex(
    MiniportAdapter *VA,
    VirtualAddress Origin,
    uint FrameSeqNo,
    uchar HopCount,
    VirtualAddress Source,
    VirtualAddress Dest,
    VRRIf LocIF,
    uchar Type)
{
    PacketIndex *PX = &VA->PX;
    PacketIndexEntry *PXE;
    uint NewPXE = FALSE;
    KIRQL OldIrql;

    if (PXE_CTL_MSG_ONLY && Type == VRR_OPTION_TYPE_PACKET)
        return FALSE;
        
    KeAcquireSpinLock(&VA->PX.Lock, &OldIrql);

    //
    // PXE have unique keys (Origin,FrameSeqNo).
    //
    if ((PXE=FindPXE(PX, Origin,FrameSeqNo,Type)) == NULL) {
        NewPXE = TRUE;
        if ((PXE=CreatePXE(Origin,FrameSeqNo,Type)) != NULL)
            InsertPXE(VA, PXE);
    }

    //
    // Update non-key fields within the PXE.
    //
    if (PXE != NULL) {
        PXE->Timeout = KeQueryInterruptTime() + PACKET_INDEX_LIFETIME;
        PXE->HopCount = HopCount;
        RtlCopyMemory(PXE->Source,Source,sizeof(VirtualAddress));
        RtlCopyMemory(PXE->Dest,Dest,sizeof(VirtualAddress));
        PXE->LocIF = LocIF;
        PXE->Timeout = KeQueryInterruptTime() + PACKET_INDEX_LIFETIME;
    }

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

    return NewPXE;
}


//* PacketIndexCleanup
//
// Flush the Packet Index.
//
void
PacketIndexCleanup(
    MiniportAdapter *VA)
{
    PacketIndexEntry *PXE;
    PacketIndex *PX = &VA->PX;
    KIRQL OldIrql;

    KeAcquireSpinLock(&VA->PX.Lock, &OldIrql);
    while ((PXE = PX->FirstPXE) != SentinelPXE(PX))
        RemovePXE(PX, PXE);
    KeReleaseSpinLock(&VA->PX.Lock, OldIrql);
}

//* PacketIndexTimeout
//
//  Housekeeping of Packet Index.
//
Time
PacketIndexTimeout(
    MiniportAdapter *VA,
    Time Now)
{
    NDIS_STATUS Status;
    LARGE_INTEGER Timestamp;
    LARGE_INTEGER Frequency;
    KIRQL OldIrql;
    Time NextTimeout = Now + MIN_PXE_TIMOUT_INTERVAL;
    PacketIndex *PX = &VA->PX;
    PacketIndexEntry *PXE;
    PacketIndexEntry *NextPXE;

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

    for (PXE = VA->PX.FirstPXE;
         PXE != SentinelPXE(&VA->PX);
         PXE = NextPXE) {

        Time PXETimeout = PXE->Timeout;

        NextPXE = PXE->Next;

        if (PXETimeout < Now)
            RemovePXE(PX,PXE);

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

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

    return NextTimeout;
}