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

//
// Implements support for partition repair.
//

#include "headers.h"

// ZL:
//* ZeroListInit
//
//  Initialize Zero List for partition repair protocol.
//
void
ZeroListInit(ZeroList *ZL)
{
    const Time Centuries400 = ((Time)MINUTE * 60 * 24 * 365 * 399);
    Time SystemTime;

    KeInitializeSpinLock(&ZL->Lock);
    ZL->FirstZLE = ZL->LastZLE = SentinelZLE(ZL);
}

//* GetZeroSeqNo
//
//  Return SeqNo derived from system clock.
//
uint
GetZeroSeqNo()
{
    const Time Centuries400 = ((Time)MINUTE * 60 * 24 * 365 * 399);
    Time SystemTime;

    //
    // Seconds since 1 Jan 2000, approx.
    // KeQuerySystemTime() returns 100ns since 1 Jan 1601.
    //
    KeQuerySystemTime((LARGE_INTEGER *)&SystemTime);
    SystemTime -= Centuries400;
    return TIME_TO_MS(SystemTime) / 1000;
}


//* RemoveZLE
void
RemoveZLE(
    ZeroList *ZL,
    ZeroListEntry *ZLE)
{
    //
    // Sanity checks.
    //
    VRRASSERT(ZLE != (ZeroListEntry *)ZL);

    //
    // Adjust pointers and free memory.
    //
    ZLE->Next->Prev = ZLE->Prev;
    ZLE->Prev->Next = ZLE->Next;
}

//* RemoveAndFreeZLE
void
RemoveAndFreeZLE(
    ZeroList *ZL,
    ZeroListEntry *ZLE)
{
    RemoveZLE(ZL,ZLE);
    ExFreePool(ZLE);
}


//* InsertZLE
//
//  Insert ZLE into Zero List.
//
//  Caller must hold the ZL->Lock.
//
void
InsertZLE(
    MiniportAdapter *VA,
    ZeroListEntry *ZLE)
{
    ZeroList *ZL = &VA->ZL;
    ZeroListEntry *NextZLE;
    __int64 DistZeroZLE = Uint64VirtualAddressDistance(VirtualAddressToUint64(ZLE->Address),
                                                       VirtualAddressToUint64(NullAddress));

    VRRASSERT(ZL != NULL);
    VRRASSERT(ZLE != NULL);

    //
    // Find insertion point for the ZLE in the Zero List.
    //
    for (NextZLE = ZL->FirstZLE; 
         NextZLE != SentinelZLE(ZL);
         NextZLE = NextZLE->Next) {

        __int64 DistZeroNextZLE;

        //
        // Active before expired, ordered by closest(zero).
        //
        if (ZLE->State == ZLE_STATE_ACTIVE &&
            NextZLE->State != ZLE_STATE_ACTIVE)
            break;

        DistZeroNextZLE = Uint64VirtualAddressDistance(VirtualAddressToUint64(NextZLE->Address),
                                                       VirtualAddressToUint64(NullAddress));

        if (DistZeroZLE < DistZeroNextZLE)
            break;

        if (DistZeroZLE == DistZeroNextZLE &&
            IsCloserRight(ZLE->Address, NextZLE->Address, NullAddress))
            break;
    }

    //
    // Insert the new ZLE immediately prior to NextZLE.
    //
    ZLE->Prev = NextZLE->Prev;
    ZLE->Prev->Next = ZLE;
    ZLE->Next = NextZLE;
    ZLE->Next->Prev = ZLE;
   
}

//* CreateZLE
//
//  Allocate a new Zero List Entry in memory.
//
ZeroListEntry *
CreateZLE(
    VirtualAddress Address)
{
    ZeroListEntry *ZLE;

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

    //
    // Initialize the ZLE.
    //
    RtlZeroMemory(ZLE, sizeof *ZLE);
    RtlCopyMemory(ZLE->Address,Address,sizeof(VirtualAddress));

    return ZLE;
}

//* FindZLE
//
//  Returns ZLE iff in Zero List, else NULL.
//
//  Caller must hold the ZL->Lock.
//
ZeroListEntry *
FindZLE(
    ZeroList *ZL,
    VirtualAddress Address)
{
    ZeroListEntry *ZLE;

    VRRASSERT(ZL != NULL);

    for (ZLE = ZL->FirstZLE; 
         ZLE != SentinelZLE(ZL);
         ZLE = ZLE->Next) {
         
        if (VirtualAddressEqual(ZLE->Address, Address))
            return ZLE;
    }

    return NULL;    
}

//* UpdateZLE
//
//
ZeroListEntry *
UpdateZLE(
    MiniportAdapter *VA,
    VirtualAddress Address,
    uint SeqNo)
{
    ZeroList *ZL = &VA->ZL;
    ZeroListEntry *ZLE;
        
    if ((ZLE=FindZLE(ZL, Address)) != NULL)
        if (SeqNo > ZLE->SeqNo)
            ZLE->SeqNo = SeqNo;
        else
            return NULL;
    else if ((ZLE=CreateZLE(Address)) != NULL) {
        ZLE->SeqNo = SeqNo;
        InsertZLE(VA, ZLE);
    }

    if (ZLE == NULL)
        return NULL;

    ZLE->Timeout = KeQueryInterruptTime() + HelloLifetime;

    //
    // The update may cause a ZLE state transition.
    //
    if (ZLE->State != ZLE_STATE_ACTIVE) {
        RemoveZLE(&VA->ZL,ZLE);
        ZLE->State = ZLE_STATE_ACTIVE;
        InsertZLE(VA,ZLE);
    }

    return ZLE;
}

//* FindAndDeleteZLE
//
//  Deletes entry from Zero List if the entry exists.
//
//  Caller must hold the ZL->Lock.
//
ZeroListEntry *
FindAndDeleteZLE(
    ZeroList *ZL,
    VirtualAddress Address)
{
    ZeroListEntry *ZLE;
        
    if ((ZLE = FindZLE(ZL, Address)) != NULL)
        RemoveAndFreeZLE(ZL, ZLE);
        
    return ZLE;
}

//* ZeroListCleanup
//
// Flush the Zero List.
//
void
ZeroListCleanup(
    MiniportAdapter *VA)
{
    ZeroListEntry *ZLE;
    ZeroList *ZL = &VA->ZL;
    KIRQL OldIrql;

    KeAcquireSpinLock(&VA->ZL.Lock, &OldIrql);
    while ((ZLE = ZL->FirstZLE) != SentinelZLE(ZL))
        RemoveAndFreeZLE(ZL, ZLE);
    KeReleaseSpinLock(&VA->ZL.Lock, OldIrql);
}

//* ZeroListTimeout
//
//  Housekeeping of Zero List.
//
Time
ZeroListTimeout(
    MiniportAdapter *VA,
    Time Now)
{
    NDIS_STATUS Status;
    LARGE_INTEGER Timestamp;
    LARGE_INTEGER Frequency;
    KIRQL OldIrql;
    Time NextTimeout = Now + ZLE_TIMEOUT_INTERVAL;
    ZeroList *ZL = &VA->ZL;
    ZeroListEntry *ZLE;
    ZeroListEntry *NextZLE;

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

    for (ZLE = VA->ZL.FirstZLE;
         ZLE != SentinelZLE(&VA->ZL);
         ZLE = NextZLE) {

        Time ZLETimeout = ZLE->Timeout;

        NextZLE = ZLE->Next;

        //
        // Check for transition from ACTIVE state.
        //
        if (ZLE->State == ZLE_STATE_ACTIVE &&
            ZLETimeout <= Now) {

            RemoveZLE(ZL,ZLE);
            ZLE->State = ZLE_STATE_STALE;
            InsertZLE(VA,ZLE);
        }

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