Re: [win-pv-devel] [PATCH 05/10] Use a hash table for event channel lookup

[Paul Durrant <Paul.Durrant@xxxxxxxxxx>]

> -----Original Message-----
> From: Paul Durrant [mailto:paul.durrant@xxxxxxxxxx]
> Sent: 06 November 2014 14:24
> To: win-pv-devel@xxxxxxxxxxxxxxxxxxxx
> Cc: Paul Durrant
> Subject: [PATCH 05/10] Use a hash table for event channel lookup
> 
> Rather than using a large array for mapping port values to channel
> structures, use a hash table. This means we no longer need to code a
> hard port number limit into the EVTCHN implementation.
> 
> Because the hash table implementation manages its own locking, we also no
> longer need to make such liberal use of the interrupt lock in the EVTCHN
> implementation and can use the spinlock instead.
> 
> Signed-off-by: Paul Durrant <paul.durrant@xxxxxxxxxx>

There was some character encoding weirdness which unfortunately meant two 
slightly different variants of this patch were posted. There is no functional 
difference.

  Paul

> ---
>  include/evtchn_interface.h      |   4 +-
>  include/shared_info_interface.h |   3 -
>  src/xenbus/evtchn.c             |  89 ++++++----
>  src/xenbus/hash_table.c         | 367
> ++++++++++++++++++++++++++++++++++++++++
>  src/xenbus/hash_table.h         |  70 ++++++++
>  src/xenbus/shared_info.c        |   3 +
>  vs2012/xenbus/xenbus.vcxproj    |   1 +
>  vs2013/xenbus/xenbus.vcxproj    |   3 +-
>  8 files changed, 504 insertions(+), 36 deletions(-)
>  create mode 100644 src/xenbus/hash_table.c
>  create mode 100644 src/xenbus/hash_table.h
> 
> diff --git a/include/evtchn_interface.h b/include/evtchn_interface.h
> index 991d610..3a48915 100644
> --- a/include/evtchn_interface.h
> +++ b/include/evtchn_interface.h
> @@ -117,14 +117,14 @@ typedef PXENBUS_EVTCHN_CHANNEL
> 
>      \param Interface The interface header
>      \param Channel The channel handle
> -    \param Locked Set to TRUE if this method is invoked in context of the
> channel callback
> +    \param InCallback Set to TRUE if this method is invoked in context of the
> channel callback
>      \return TRUE if there was an event pending at the point of unmask, FALSE
> otherwise
>  */
>  typedef BOOLEAN
>  (*XENBUS_EVTCHN_UNMASK)(
>      IN  PINTERFACE              Interface,
>      IN  PXENBUS_EVTCHN_CHANNEL  Channel,
> -    IN  BOOLEAN                 Locked
> +    IN  BOOLEAN                 InCallback
>      );
> 
>  /*! \typedef XENBUS_EVTCHN_SEND
> diff --git a/include/shared_info_interface.h
> b/include/shared_info_interface.h
> index 0d36ac8..0e5a0d7 100644
> --- a/include/shared_info_interface.h
> +++ b/include/shared_info_interface.h
> @@ -40,9 +40,6 @@
> 
>  #ifndef _WINDLL
> 
> -#define XENBUS_SHARED_INFO_EVTCHN_PER_SELECTOR     (sizeof
> (ULONG_PTR) * 8)
> -#define XENBUS_SHARED_INFO_EVTCHN_SELECTOR_COUNT
> (RTL_FIELD_SIZE(shared_info_t, evtchn_pending) / sizeof (ULONG_PTR))
> -
>  /*! \typedef XENBUS_SHARED_INFO_ACQUIRE
>      \brief Acquire a reference to the SHARED_INFO interface
> 
> diff --git a/src/xenbus/evtchn.c b/src/xenbus/evtchn.c
> index 35ad44a..338a90f 100644
> --- a/src/xenbus/evtchn.c
> +++ b/src/xenbus/evtchn.c
> @@ -36,6 +36,7 @@
> 
>  #include "evtchn.h"
>  #include "fdo.h"
> +#include "hash_table.h"
>  #include "dbg_print.h"
>  #include "assert.h"
> 
> @@ -97,7 +98,7 @@ struct _XENBUS_EVTCHN_CONTEXT {
>      XENBUS_DEBUG_INTERFACE          DebugInterface;
>      PXENBUS_DEBUG_CALLBACK          DebugCallback;
>      XENBUS_SHARED_INFO_INTERFACE    SharedInfoInterface;
> -    PXENBUS_EVTCHN_CHANNEL
> Channel[XENBUS_SHARED_INFO_EVTCHN_SELECTOR_COUNT *
> XENBUS_SHARED_INFO_EVTCHN_PER_SELECTOR];
> +    PXENBUS_HASH_TABLE              Table;
>      LIST_ENTRY                      List;
>  };
> 
> @@ -351,14 +352,16 @@ EvtchnOpen(
> 
>      LocalPort = Channel->LocalPort;
> 
> -    ASSERT3U(LocalPort, <, sizeof (Context->Channel) / sizeof (Context-
> >Channel[0]));
> -
> -    (VOID) __EvtchnAcquireInterruptLock(Context);
> +    status = HashTableAdd(Context->Table,
> +                          LocalPort,
> +                          (ULONG_PTR)Channel);
> +    if (!NT_SUCCESS(status))
> +        goto fail3;
> 
> -    ASSERT3P(Context->Channel[LocalPort], ==, NULL);
> -    Context->Channel[LocalPort] = Channel;
>      Channel->Active = TRUE;
> 
> +    KeAcquireSpinLockAtDpcLevel(&Context->Lock);
> +
>      InsertTailList(&Context->List, &Channel->ListEntry);
> 
>      if (!IsListEmpty(&Context->List) && !Context->Enabled) {
> @@ -366,12 +369,18 @@ EvtchnOpen(
>          Context->Enabled = TRUE;
>      }
> 
> -    __EvtchnReleaseInterruptLock(Context, DISPATCH_LEVEL);
> +    KeReleaseSpinLockFromDpcLevel(&Context->Lock);
> 
>      KeLowerIrql(Irql);
> 
>      return Channel;
> 
> +fail3:
> +    Error("fail3\n");
> +
> +    Channel->LocalPort = 0;
> +    RtlZeroMemory(&Channel->Parameters, sizeof
> (XENBUS_EVTCHN_PARAMETERS));
> +
>  fail2:
>      Error("fail2\n");
> 
> @@ -398,7 +407,7 @@ static BOOLEAN
>  EvtchnUnmask(
>      IN  PINTERFACE              Interface,
>      IN  PXENBUS_EVTCHN_CHANNEL  Channel,
> -    IN  BOOLEAN                 Locked
> +    IN  BOOLEAN                 InCallback
>      )
>  {
>      PXENBUS_EVTCHN_CONTEXT      Context = Interface->Context;
> @@ -407,8 +416,10 @@ EvtchnUnmask(
> 
>      ASSERT3U(Channel->Magic, ==, XENBUS_EVTCHN_CHANNEL_MAGIC);
> 
> -    if (!Locked)
> -        Irql = __EvtchnAcquireInterruptLock(Context);
> +    if (!InCallback)
> +        KeRaiseIrql(DISPATCH_LEVEL, &Irql); // Prevent suspend
> +
> +    ASSERT3U(KeGetCurrentIrql(), >=, DISPATCH_LEVEL);
> 
>      if (Channel->Active) {
>          Pending = XENBUS_SHARED_INFO(EvtchnUnmask,
> @@ -446,8 +457,8 @@ EvtchnUnmask(
>          }
>      }
> 
> -    if (!Locked)
> -        __EvtchnReleaseInterruptLock(Context, Irql);
> +    if (!InCallback)
> +        KeLowerIrql(Irql);
> 
>      return Pending;
>  }
> @@ -513,6 +524,8 @@ EvtchnTrigger(
> 
>      Irql = __EvtchnAcquireInterruptLock(Context);
> 
> +    ASSERT3U(KeGetCurrentIrql(), >=, DISPATCH_LEVEL);
> +
>      if (Channel->Active) {
>          DoneSomething = EvtchnCallback(Context, Channel);
>      } else {
> @@ -536,7 +549,9 @@ EvtchnClose(
> 
>      ASSERT3U(Channel->Magic, ==, XENBUS_EVTCHN_CHANNEL_MAGIC);
> 
> -    Irql = __EvtchnAcquireInterruptLock(Context);
> +    KeRaiseIrql(DISPATCH_LEVEL, &Irql); // Prevent suspend
> +
> +    KeAcquireSpinLockAtDpcLevel(&Context->Lock);
> 
>      RemoveEntryList(&Channel->ListEntry);
> 
> @@ -545,12 +560,13 @@ EvtchnClose(
>          Context->Enabled = FALSE;
>      }
> 
> +    KeReleaseSpinLockFromDpcLevel(&Context->Lock);
> +
>      RtlZeroMemory(&Channel->ListEntry, sizeof (LIST_ENTRY));
> 
>      if (Channel->Active) {
> -        ULONG   LocalPort = Channel->LocalPort;
> -
> -        ASSERT3U(LocalPort, <, sizeof (Context->Channel) / sizeof (Context-
> >Channel[0]));
> +        ULONG       LocalPort = Channel->LocalPort;
> +        NTSTATUS    status;
> 
>          Channel->Active = FALSE;
> 
> @@ -561,12 +577,10 @@ EvtchnClose(
>          if (Channel->Type != XENBUS_EVTCHN_TYPE_FIXED)
>              (VOID) EventChannelClose(LocalPort);
> 
> -        ASSERT(Context->Channel[LocalPort] != NULL);
> -        Context->Channel[LocalPort] = NULL;
> +        status = HashTableRemove(Context->Table, LocalPort);
> +        ASSERT(NT_SUCCESS(status));
>      }
> 
> -    __EvtchnReleaseInterruptLock(Context, Irql);
> -
>      Channel->LocalPort = 0;
>      RtlZeroMemory(&Channel->Parameters, sizeof
> (XENBUS_EVTCHN_PARAMETERS));
> 
> @@ -580,6 +594,8 @@ EvtchnClose(
> 
>      ASSERT(IsZeroMemory(Channel, sizeof (XENBUS_EVTCHN_CHANNEL)));
>      __EvtchnFree(Channel);
> +
> +    KeLowerIrql(Irql);
>  }
> 
>  static ULONG
> @@ -606,12 +622,13 @@ EvtchnPollCallback(
>      PXENBUS_EVTCHN_CHANNEL  Channel;
>      BOOLEAN                 Mask;
>      BOOLEAN                 DoneSomething;
> +    NTSTATUS                status;
> 
> -    ASSERT3U(LocalPort, <, sizeof (Context->Channel) / sizeof (Context-
> >Channel[0]));
> -
> -    Channel = Context->Channel[LocalPort];
> -
> -    if (Channel == NULL) {
> +    status = HashTableLookup(Context->Table,
> +                             LocalPort,
> +                             (PULONG_PTR)&Channel);
> +
> +    if (!NT_SUCCESS(status)) {
>          Warning("[%d]: INVALID PORT\n", LocalPort);
> 
>          XENBUS_SHARED_INFO(EvtchnMask,
> @@ -697,14 +714,13 @@ EvtchnSuspendCallbackEarly(
>          Channel = CONTAINING_RECORD(ListEntry,
> XENBUS_EVTCHN_CHANNEL, ListEntry);
> 
>          if (Channel->Active) {
> -            ULONG   LocalPort = Channel->LocalPort;
> -
> -            ASSERT3U(LocalPort, <, sizeof (Context->Channel) / sizeof 
> (Context-
> >Channel[0]));
> +            ULONG       LocalPort = Channel->LocalPort;
> +            NTSTATUS    status;
> 
>              Channel->Active = FALSE;
> 
> -            ASSERT(Context->Channel[LocalPort] != NULL);
> -            Context->Channel[LocalPort] = NULL;
> +            status = HashTableRemove(Context->Table, LocalPort);
> +            ASSERT(NT_SUCCESS(status));
>          }
>      }
> 
> @@ -958,6 +974,10 @@ EvtchnInitialize(
>      if (*Context == NULL)
>          goto fail1;
> 
> +    status = HashTableCreate(&(*Context)->Table);
> +    if (!NT_SUCCESS(status))
> +        goto fail2;
> +
>      status = SuspendGetInterface(FdoGetSuspendContext(Fdo),
>                                   XENBUS_SUSPEND_INTERFACE_VERSION_MAX,
>                                   (PINTERFACE)&(*Context)->SuspendInterface,
> @@ -988,6 +1008,12 @@ EvtchnInitialize(
> 
>      return STATUS_SUCCESS;
> 
> +fail2:
> +    Error("fail2\n");
> +
> +    ASSERT(IsZeroMemory(Context, sizeof (XENBUS_EVTCHN_CONTEXT)));
> +    __EvtchnFree(Context);
> +
>  fail1:
>      Error("fail1 (%08x)\n", status);
> 
> @@ -1053,6 +1079,9 @@ EvtchnTeardown(
>      RtlZeroMemory(&Context->SuspendInterface,
>                    sizeof (XENBUS_SUSPEND_INTERFACE));
> 
> +    HashTableDestroy(Context->Table);
> +    Context->Table = NULL;
> +
>      ASSERT(IsZeroMemory(Context, sizeof (XENBUS_EVTCHN_CONTEXT)));
>      __EvtchnFree(Context);
> 
> diff --git a/src/xenbus/hash_table.c b/src/xenbus/hash_table.c
> new file mode 100644
> index 0000000..b8e27d8
> --- /dev/null
> +++ b/src/xenbus/hash_table.c
> @@ -0,0 +1,367 @@
> +/* Copyright (c) Citrix Systems Inc.
> + * All rights reserved.
> + *
> + * Redistribution and use in source and binary forms,
> + * with or without modification, are permitted provided
> + * that the following conditions are met:
> + *
> + * *   Redistributions of source code must retain the above
> + *     copyright notice, this list of conditions and the
> + *     following disclaimer.
> + * *   Redistributions in binary form must reproduce the above
> + *     copyright notice, this list of conditions and the
> + *     following disclaimer in the documentation and/or other
> + *     materials provided with the distribution.
> + *
> + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
> + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
> + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
> + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
> + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
> + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
> + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
> + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
> + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
> + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
> + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
> + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> + * SUCH DAMAGE.
> + */
> +
> +#include <ntddk.h>
> +#include <stdarg.h>
> +#include <xen.h>
> +#include <util.h>
> +
> +#include "hash_table.h"
> +#include "dbg_print.h"
> +#include "assert.h"
> +
> +typedef struct _XENBUS_HASH_TABLE_NODE {
> +    LIST_ENTRY  ListEntry;
> +    ULONG_PTR   Key;
> +    ULONG_PTR   Value;
> +} XENBUS_HASH_TABLE_NODE, *PXENBUS_HASH_TABLE_NODE;
> +
> +typedef struct _XENBUS_HASH_TABLE_BUCKET {
> +    LONG        Lock;
> +    LIST_ENTRY  List;
> +} XENBUS_HASH_TABLE_BUCKET, *PXENBUS_HASH_TABLE_BUCKET;
> +
> +#define XENBUS_HASH_TABLE_NR_BUCKETS \
> +    (1 << (sizeof (UCHAR) * 8))
> +
> +struct _XENBUS_HASH_TABLE {
> +    XENBUS_HASH_TABLE_BUCKET
> Bucket[XENBUS_HASH_TABLE_NR_BUCKETS];
> +};
> +
> +#define XENBUS_HASH_TABLE_TAG   'HSAH'
> +
> +static FORCEINLINE PVOID
> +__HashTableAllocate(
> +    IN  ULONG   Length
> +    )
> +{
> +    return __AllocatePoolWithTag(NonPagedPool, Length,
> XENBUS_HASH_TABLE_TAG);
> +}
> +
> +static FORCEINLINE VOID
> +__HashTableFree(
> +    IN  PVOID   Buffer
> +    )
> +{
> +    ExFreePoolWithTag(Buffer, XENBUS_HASH_TABLE_TAG);
> +}
> +
> +static ULONG
> +HashTableHash(
> +    IN  ULONG_PTR   Key
> +    )
> +{
> +    PUCHAR          Array = (PUCHAR)&Key;
> +    ULONG           Accumulator;
> +    ULONG           Index;
> +
> +    Accumulator = 0;
> +
> +    for (Index = 0; Index < sizeof (ULONG_PTR); Index++) {
> +        ULONG   Overflow;
> +
> +        Accumulator = (Accumulator << 4) + Array[Index];
> +
> +        Overflow = Accumulator & 0x00000f00;
> +        if (Overflow != 0) {
> +            Accumulator ^= Overflow >> 8;
> +            Accumulator ^= Overflow;
> +        }
> +    }
> +
> +    ASSERT3U(Accumulator, <, XENBUS_HASH_TABLE_NR_BUCKETS);
> +
> +    return Accumulator;
> +}
> +
> +static
> +_IRQL_requires_max_(HIGH_LEVEL)
> +_IRQL_saves_
> +_IRQL_raises_(HIGH_LEVEL)
> +KIRQL
> +__HashTableBucketLock(
> +    IN  PXENBUS_HASH_TABLE_BUCKET   Bucket,
> +    IN  BOOLEAN                     Writer
> +    )
> +{
> +    KIRQL                           Irql;
> +
> +    KeRaiseIrql(HIGH_LEVEL, &Irql);
> +
> +    for (;;) {
> +        LONG    Lock;
> +        LONG    Readers;
> +        LONG    Writers;
> +        LONG    Old;
> +        LONG    New;
> +
> +        KeMemoryBarrier();
> +
> +        Lock = Bucket->Lock;
> +        Readers = Lock >> 1;
> +        Writers = Lock & 1;
> +
> +        // There must be no existing writer
> +        Old = Readers << 1;
> +
> +        if (Writer)
> +            Writers++;
> +        else
> +            Readers++;
> +
> +        New = (Readers << 1) | (Writers & 1);
> +
> +        if (InterlockedCompareExchange(&Bucket->Lock, New, Old) != Old)
> +            continue;
> +
> +        //
> +        // We are done if we're not a writer, or there are no readers
> +        // left.
> +        //
> +        if (!Writer || Readers == 0)
> +            break;
> +    }
> +
> +    return Irql;
> +}
> +
> +#define HashTableBucketLock(_Bucket, _Writer, _Irql)            \
> +    do {                                                        \
> +        *(_Irql) = __HashTableBucketLock((_Bucket), (_Writer)); \
> +    } while (FALSE)
> +
> +static
> +__drv_requiresIRQL(HIGH_LEVEL)
> +VOID
> +HashTableBucketUnlock(
> +    IN  PXENBUS_HASH_TABLE_BUCKET   Bucket,
> +    IN  BOOLEAN                     Writer,
> +    IN  __drv_restoresIRQL KIRQL    Irql
> +    )
> +{
> +    for (;;) {
> +        LONG    Lock;
> +        LONG    Readers;
> +        LONG    Writers;
> +        LONG    Old;
> +        LONG    New;
> +
> +        KeMemoryBarrier();
> +
> +        Lock = Bucket->Lock;
> +        Readers = Lock >> 1;
> +        Writers = Lock & 1;
> +
> +        Old = (Readers << 1) | (Writers & 1);
> +
> +        if (Writer) {
> +            ASSERT(Writers != 0);
> +            --Writers;
> +        } else {
> +            --Readers;
> +        }
> +
> +        New = (Readers << 1) | (Writers & 1);
> +
> +        if (InterlockedCompareExchange(&Bucket->Lock, New, Old) == Old)
> +            break;
> +    }
> +
> +    KeLowerIrql(Irql);
> +}
> +
> +NTSTATUS
> +HashTableAdd(
> +    IN  PXENBUS_HASH_TABLE      Table,
> +    IN  ULONG_PTR               Key,
> +    IN  ULONG_PTR               Value
> +    )
> +{
> +    PXENBUS_HASH_TABLE_NODE     Node;
> +    PXENBUS_HASH_TABLE_BUCKET   Bucket;
> +    KIRQL                       Irql;
> +    NTSTATUS                    status;
> +
> +    Node = __HashTableAllocate(sizeof (XENBUS_HASH_TABLE_NODE));
> +
> +    status = STATUS_NO_MEMORY;
> +    if (Node == NULL)
> +        goto fail1;
> +
> +    Node->Key = Key;
> +    Node->Value = Value;
> +
> +    Bucket = &Table->Bucket[HashTableHash(Key)];
> +
> +    HashTableBucketLock(Bucket, TRUE, &Irql);
> +    InsertTailList(&Bucket->List, &Node->ListEntry);
> +    HashTableBucketUnlock(Bucket, TRUE, Irql);
> +
> +    return STATUS_SUCCESS;
> +
> +fail1:
> +    Error("fail1 (%08x)\n", status);
> +
> +    return status;
> +}
> +
> +NTSTATUS
> +HashTableRemove(
> +    IN  PXENBUS_HASH_TABLE      Table,
> +    IN  ULONG_PTR               Key
> +    )
> +{
> +    PXENBUS_HASH_TABLE_BUCKET   Bucket;
> +    PLIST_ENTRY                 ListEntry;
> +    PXENBUS_HASH_TABLE_NODE     Node;
> +    KIRQL                       Irql;
> +    NTSTATUS                    status;
> +
> +    Bucket = &Table->Bucket[HashTableHash(Key)];
> +
> +    HashTableBucketLock(Bucket, TRUE, &Irql);
> +
> +    ListEntry = Bucket->List.Flink;
> +    while (ListEntry != &Bucket->List) {
> +        Node = CONTAINING_RECORD(ListEntry, XENBUS_HASH_TABLE_NODE,
> ListEntry);
> +
> +        if (Node->Key == Key)
> +            goto found;
> +    }
> +
> +    HashTableBucketUnlock(Bucket, TRUE, Irql);
> +
> +    status = STATUS_OBJECT_NAME_NOT_FOUND;
> +    goto fail1;
> +
> +found:
> +    RemoveEntryList(ListEntry);
> +    __HashTableFree(Node);
> +
> +    HashTableBucketUnlock(Bucket, TRUE, Irql);
> +
> +    return STATUS_SUCCESS;
> +
> +fail1:
> +    Error("fail1 (%08x)\n", status);
> +
> +    return status;
> +}
> +
> +NTSTATUS
> +HashTableLookup(
> +    IN  PXENBUS_HASH_TABLE      Table,
> +    IN  ULONG_PTR               Key,
> +    OUT PULONG_PTR              Value
> +    )
> +{
> +    PXENBUS_HASH_TABLE_BUCKET   Bucket;
> +    PLIST_ENTRY                 ListEntry;
> +    PXENBUS_HASH_TABLE_NODE     Node;
> +    KIRQL                       Irql;
> +    NTSTATUS                    status;
> +
> +    Bucket = &Table->Bucket[HashTableHash(Key)];
> +
> +    HashTableBucketLock(Bucket, FALSE, &Irql);
> +
> +    ListEntry = Bucket->List.Flink;
> +    while (ListEntry != &Bucket->List) {
> +        Node = CONTAINING_RECORD(ListEntry, XENBUS_HASH_TABLE_NODE,
> ListEntry);
> +
> +        if (Node->Key == Key)
> +            goto found;
> +    }
> +
> +    HashTableBucketUnlock(Bucket, FALSE, Irql);
> +
> +    status = STATUS_OBJECT_NAME_NOT_FOUND;
> +    goto fail1;
> +
> +found:
> +    *Value = Node->Value;
> +
> +    HashTableBucketUnlock(Bucket, FALSE, Irql);
> +
> +    return STATUS_SUCCESS;
> +
> +fail1:
> +    Error("fail1 (%08x)\n", status);
> +
> +    return status;
> +}
> +
> +NTSTATUS
> +HashTableCreate(
> +    OUT PXENBUS_HASH_TABLE  *Table
> +    )
> +{
> +    ULONG                   Index;
> +    NTSTATUS                status;
> +
> +    *Table = __HashTableAllocate(sizeof (XENBUS_HASH_TABLE));
> +
> +    status = STATUS_NO_MEMORY;
> +    if (*Table == NULL)
> +        goto fail1;
> +
> +    for (Index = 0; Index < XENBUS_HASH_TABLE_NR_BUCKETS; Index++) {
> +        PXENBUS_HASH_TABLE_BUCKET   Bucket = &(*Table)->Bucket[Index];
> +
> +        InitializeListHead(&Bucket->List);
> +    }
> +
> +    return STATUS_SUCCESS;
> +
> +fail1:
> +    Error("fail1 (%08x)\n", status);
> +
> +    return status;
> +}
> +
> +VOID
> +HashTableDestroy(
> +    IN  PXENBUS_HASH_TABLE  Table
> +    )
> +{
> +    ULONG                   Index;
> +
> +    for (Index = 0; Index < XENBUS_HASH_TABLE_NR_BUCKETS; Index++) {
> +        PXENBUS_HASH_TABLE_BUCKET   Bucket = &Table->Bucket[Index];
> +
> +        ASSERT(IsListEmpty(&Bucket->List));
> +        RtlZeroMemory(&Bucket->List, sizeof (LIST_ENTRY));
> +    }
> +
> +    ASSERT(IsZeroMemory(Table, sizeof (XENBUS_HASH_TABLE)));
> +    __HashTableFree(Table);
> +}
> +
> diff --git a/src/xenbus/hash_table.h b/src/xenbus/hash_table.h
> new file mode 100644
> index 0000000..ce0c906
> --- /dev/null
> +++ b/src/xenbus/hash_table.h
> @@ -0,0 +1,70 @@
> +/* Copyright (c) Citrix Systems Inc.
> + * All rights reserved.
> + *
> + * Redistribution and use in source and binary forms,
> + * with or without modification, are permitted provided
> + * that the following conditions are met:
> + *
> + * *   Redistributions of source code must retain the above
> + *     copyright notice, this list of conditions and the
> + *     following disclaimer.
> + * *   Redistributions in binary form must reproduce the above
> + *     copyright notice, this list of conditions and the
> + *     following disclaimer in the documentation and/or other
> + *     materials provided with the distribution.
> + *
> + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
> + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
> + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
> + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
> + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
> + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
> + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
> + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
> + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
> + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
> + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
> + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> + * SUCH DAMAGE.
> + */
> +
> +#ifndef _XENBUS_HASH_TABLE_H
> +#define _XENBUS_HASH_TABLE_H
> +
> +#include <ntddk.h>
> +
> +typedef struct _XENBUS_HASH_TABLE XENBUS_HASH_TABLE,
> *PXENBUS_HASH_TABLE;
> +
> +extern NTSTATUS
> +HashTableAdd(
> +    IN  PXENBUS_HASH_TABLE  Table,
> +    IN  ULONG_PTR           Key,
> +    IN  ULONG_PTR           Value
> +    );
> +
> +extern NTSTATUS
> +HashTableRemove(
> +    IN  PXENBUS_HASH_TABLE  Table,
> +    IN  ULONG_PTR           Key
> +    );
> +
> +extern NTSTATUS
> +HashTableLookup(
> +    IN  PXENBUS_HASH_TABLE  Table,
> +    IN  ULONG_PTR           Key,
> +    OUT PULONG_PTR          Value
> +    );
> +
> +extern NTSTATUS
> +HashTableCreate(
> +    OUT PXENBUS_HASH_TABLE  *Table
> +    );
> +
> +extern VOID
> +HashTableDestroy(
> +    IN  PXENBUS_HASH_TABLE  Table
> +    );
> +
> +#endif  // _XENBUS_HASH_TABLE_H
> +
> diff --git a/src/xenbus/shared_info.c b/src/xenbus/shared_info.c
> index 0afc218..67be20c 100644
> --- a/src/xenbus/shared_info.c
> +++ b/src/xenbus/shared_info.c
> @@ -38,6 +38,9 @@
>  #include "dbg_print.h"
>  #include "assert.h"
> 
> +#define XENBUS_SHARED_INFO_EVTCHN_PER_SELECTOR     (sizeof
> (ULONG_PTR) * 8)
> +#define XENBUS_SHARED_INFO_EVTCHN_SELECTOR_COUNT
> (RTL_FIELD_SIZE(shared_info_t, evtchn_pending) / sizeof (ULONG_PTR))
> +
>  struct _XENBUS_SHARED_INFO_CONTEXT {
>      PXENBUS_FDO                 Fdo;
>      KSPIN_LOCK                  Lock;
> diff --git a/vs2012/xenbus/xenbus.vcxproj b/vs2012/xenbus/xenbus.vcxproj
> index c30774e..a648bce 100644
> --- a/vs2012/xenbus/xenbus.vcxproj
> +++ b/vs2012/xenbus/xenbus.vcxproj
> @@ -99,6 +99,7 @@
>               <ClCompile Include="..\..\src\xenbus\range_set.c" />
>               <ClCompile Include="..\..\src\xenbus\balloon.c" />
>               <ClCompile Include="..\..\src\xenbus\cache.c" />
> +             <ClCompile Include="..\..\src\xenbus\hash_table.c" />
>       </ItemGroup>
>       <ItemGroup>
>               <ResourceCompile Include="..\..\src\xenbus\xenbus.rc" />
> diff --git a/vs2013/xenbus/xenbus.vcxproj b/vs2013/xenbus/xenbus.vcxproj
> index 588b0c5..2c34ed1 100644
> --- a/vs2013/xenbus/xenbus.vcxproj
> +++ b/vs2013/xenbus/xenbus.vcxproj
> @@ -1,4 +1,4 @@
> -ï<?xml version="1.0" encoding="utf-8"?>
> +<?xml version="1.0" encoding="utf-8"?>
>  <Project DefaultTargets="Build" ToolsVersion="12.0"
> xmlns="http://schemas.microsoft.com/developer/msbuild/2003";>
>    <Import Project="..\configs.props" />
>    <PropertyGroup Label="Globals">
> @@ -139,6 +139,7 @@
>      <ClCompile Include="..\..\src\xenbus\range_set.c" />
>      <ClCompile Include="..\..\src\xenbus\balloon.c" />
>      <ClCompile Include="..\..\src\xenbus\cache.c" />
> +    <ClCompile Include="..\..\src\xenbus\hash_table.c" />
>    </ItemGroup>
>    <ItemGroup>
>      <ResourceCompile Include="..\..\src\xenbus\xenbus.rc" />
> --
> 2.1.1

_______________________________________________
win-pv-devel mailing list
win-pv-devel@xxxxxxxxxxxxxxxxxxxx
http://lists.xenproject.org/cgi-bin/mailman/listinfo/win-pv-devel