[ovs-dev] [PATCH 12/15] datapath-windows: Add FixedSizedArray

Samuel Ghinet sghinet at cloudbasesolutions.com
Wed Aug 6 16:15:33 UTC 2014


Add FixedSizedArray

This fixed sized array implementation is meant to be used for datapath ports, hyper-v switch ports and
hyper-v switch nics. It is a fixed array of MAXUINT16 pointers to fixed sized array items.
The OVS_FXDARRAY_ITEM supports reference counting.
The fixed sized array will offer constant-time lookup based on port number, which is almost always the
kind of port lookup we do in the driver (the other one is by name, which is at km-um communication only).

Also, for hyper-v switch ports:
A closer look at NDIS_SWITCH_FORWARDING_DETAIL_NET_BUFFER_LIST_INFO, we see that the
port id there is 16bit wide. Therefore, we could use, in the future the fixed sized array for hyper-v switch
nics and ids as well.

In the future we may be able to build upon it a more complex structure, such as a flexible array, if the need will arise.

Signed-off-by: Samuel Ghinet <sghinet at cloudbasesolutions.com>
---
 datapath-windows/ovsext/Core/FixedSizedArray.c | 194 +++++++++++++++++++++++++
 datapath-windows/ovsext/Core/FixedSizedArray.h | 110 ++++++++++++++
 datapath-windows/ovsext/ovsext.vcxproj         |   2 +
 datapath-windows/ovsext/ovsext.vcxproj.filters |   8 +-
 datapath-windows/ovsext/precomp.h              |   1 +
 5 files changed, 314 insertions(+), 1 deletion(-)
 create mode 100644 datapath-windows/ovsext/Core/FixedSizedArray.c
 create mode 100644 datapath-windows/ovsext/Core/FixedSizedArray.h

diff --git a/datapath-windows/ovsext/Core/FixedSizedArray.c b/datapath-windows/ovsext/Core/FixedSizedArray.c
new file mode 100644
index 0000000..3f63753
--- /dev/null
+++ b/datapath-windows/ovsext/Core/FixedSizedArray.c
@@ -0,0 +1,194 @@
+/*
+Copyright 2014 Cloudbase Solutions Srl
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+http ://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+#include "FixedSizedArray.h"
+
+_Use_decl_annotations_
+BOOLEAN FxdArray_FindNextFree_Unsafe(_In_ const OVS_FIXED_SIZED_ARRAY* pArray, _Inout_ UINT16* pFirst)
+{
+    UINT16 first = 0;
+
+    OVS_CHECK(pFirst);
+
+    first = *pFirst;
+
+    //we have set the 'firstFree' to a port => we must find the next free port to set firstFree = null_port
+    //we start searching a free slot in [first, end]
+    while (first < OVS_MAX_ARRAY_SIZE && pArray->array[first])
+    {
+        first++;
+    }
+
+    //if we found a free slot => this is the free port we return
+    if (first < OVS_MAX_ARRAY_SIZE)
+    {
+        if (!pArray->array[first])
+        {
+            *pFirst = first;
+            return TRUE;
+        }
+    }
+
+    //else, search [0, first)
+    for (first = 0; first < pArray->firstFree; ++first)
+    {
+        if (!pArray->array[first])
+        {
+            *pFirst = first;
+            return TRUE;
+        }
+    }
+
+    return FALSE;
+}
+
+_Use_decl_annotations_
+OVS_ERROR FxdArray_AddByNumber_Unsafe(_Inout_ OVS_FIXED_SIZED_ARRAY* pArray, const OVS_FXDARRAY_ITEM* pItem, UINT16 number)
+{
+    UINT16 first = pArray->firstFree;
+    OVS_ERROR error = OVS_ERROR_NOERROR;
+
+    if (NULL != pArray->array[number])
+    {
+        return OVS_ERROR_EXIST;
+    }
+
+    pArray->array[number] = OVS_CONST_CAST(pItem);
+    pArray->count++;
+
+    if (first == 0)
+    {
+        OVS_CHECK(number <= MAXUINT16);
+
+        first = (UINT16)number;
+    }
+
+    if (first != number)
+    {
+        error = OVS_ERROR_INVAL;
+        goto Cleanup;
+    }
+
+    if (first == number)
+    {
+        //we have set the 'firstFree' to a port => we must find the next free port to set firstFree = null_port
+        if (!FxdArray_FindNextFree_Unsafe(pArray, &first))
+        {
+            OVS_CHECK(pArray->count == MAXUINT16);
+
+            LOG_ERROR("all available ports are used!\n");
+            error = OVS_ERROR_NOSPC;
+            goto Cleanup;
+        }
+
+        pArray->firstFree = first;
+    }
+
+Cleanup:
+    if (error)
+    {
+        //found no room for new port
+        pArray->array[number] = NULL;
+        pArray->count--;
+    }
+
+    return error;
+}
+
+_Use_decl_annotations_
+BOOLEAN FxdArray_Add_Unsafe(_Inout_ OVS_FIXED_SIZED_ARRAY* pArray, const OVS_FXDARRAY_ITEM* pItem, UINT16* pNumber)
+{
+    UINT16 first = pArray->firstFree;
+    UINT16 number = 0;
+    BOOLEAN ok = TRUE;
+
+    OVS_CHECK(NULL == pArray->array[first]);
+    number = first;
+
+    pArray->array[number] = OVS_CONST_CAST(pItem);
+    pArray->count++;
+
+    if (!FxdArray_FindNextFree_Unsafe(pArray, &first))
+    {
+        OVS_CHECK(pArray->count == MAXUINT16);
+
+        LOG_ERROR("all available ports are used!\n");
+        ok = FALSE;
+        goto Cleanup;
+    }
+
+    pArray->firstFree = first;
+
+Cleanup:
+    if (ok)
+    {
+        *pNumber = number;
+    }
+    else
+    {
+        //found no room for new port
+        pArray->array[number] = NULL;
+        pArray->count--;
+    }
+
+    return ok;
+}
+
+_Use_decl_annotations_
+OVS_FXDARRAY_ITEM* FxdArray_Find_Unsafe(const OVS_FIXED_SIZED_ARRAY* pArray, FxdArrayCondition condition, const VOID* pCondData)
+{
+    OVS_FXDARRAY_ITEM* pOutItem = NULL;
+
+    OVS_FXDARRAY_FOR_EACH(pArray, pCurItem, /*if*/ condition(pCurItem, (UINT_PTR)pCondData),
+        pOutItem = OVS_REFCOUNT_REFERENCE(pCurItem)
+        );
+
+    return pOutItem;
+}
+
+_Use_decl_annotations_
+OVS_FXDARRAY_ITEM* FxdArray_Find_Ref(const OVS_FIXED_SIZED_ARRAY* pArray, FxdArrayCondition condition, const VOID* pCondData)
+{
+    OVS_FXDARRAY_ITEM* pOutItem = NULL;
+    LOCK_STATE_EX lockState;
+
+    FXARRAY_LOCK_READ(pArray, &lockState);
+
+    pOutItem = FxdArray_Find_Unsafe(pArray, condition, pCondData);
+
+    FXARRAY_UNLOCK(pArray, &lockState);
+
+    return pOutItem;
+}
+
+BOOLEAN FxdArray_Remove_Unsafe(OVS_FIXED_SIZED_ARRAY* pArray, OVS_FXDARRAY_ITEM* pItem, UINT16 number)
+{
+    if (pArray->array[number] != pItem)
+    {
+        LOG_ERROR(__FUNCTION__ "item not found: %u\n", number);
+        return FALSE;
+    }
+
+    OVS_CHECK(number <= 0xFFFF);
+    pArray->array[number] = NULL;
+
+    pArray->firstFree = number;
+
+    OVS_CHECK(pArray->count > 0);
+    --(pArray->count);
+
+    return TRUE;
+}
diff --git a/datapath-windows/ovsext/Core/FixedSizedArray.h b/datapath-windows/ovsext/Core/FixedSizedArray.h
new file mode 100644
index 0000000..08dddb3
--- /dev/null
+++ b/datapath-windows/ovsext/Core/FixedSizedArray.h
@@ -0,0 +1,110 @@
+/*
+Copyright 2014 Cloudbase Solutions Srl
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+http ://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+#pragma once
+
+#include "precomp.h"
+
+#include "Error.h"
+
+#define OVS_MAX_ARRAY_SIZE      MAXUINT16
+
+typedef struct _OVS_FXDARRAY_ITEM OVS_FXDARRAY_ITEM;
+
+typedef BOOLEAN (*FxdArrayCondition)(OVS_FXDARRAY_ITEM* pItem, UINT_PTR data);
+
+//specific item entries inherit OVS_FXDARRAY_ITEM
+typedef struct _OVS_FXDARRAY_ITEM
+{
+    //must be the first field in the struct
+    OVS_REF_COUNT refCount;
+
+    NDIS_RW_LOCK_EX* pRwLock;
+}OVS_FXDARRAY_ITEM, *POVS_FXDARRAY_ITEM;
+
+#define FXDITEM_LOCK_READ(pItem, pLockState) NdisAcquireRWLockRead((pItem)->pRwLock, pLockState, 0)
+#define FXDITEM_LOCK_WRITE(pItem, pLockState) NdisAcquireRWLockWrite((pItem)->pRwLock, pLockState, 0)
+#define FXDITEM_UNLOCK(pItem, pLockState) NdisReleaseRWLock((pItem)->pRwLock, pLockState)
+
+typedef struct _OVS_FIXED_SIZED_ARRAY
+{
+    NDIS_RW_LOCK_EX* pRwLock;
+
+    OVS_FXDARRAY_ITEM* array[OVS_MAX_ARRAY_SIZE];
+    UINT16 count;
+    UINT16 firstFree;
+}OVS_FIXED_SIZED_ARRAY;
+
+#define FXDARRAY_LOCK_READ(pArray, pLockState) NdisAcquireRWLockRead((pArray)->pRwLock, pLockState, 0)
+#define FXDARRAY_LOCK_WRITE(pArray, pLockState) NdisAcquireRWLockWrite((pArray)->pRwLock, pLockState, 0)
+#define FXDARRAY_UNLOCK(pArray, pLockState) NdisReleaseRWLock((pArray)->pRwLock, pLockState)
+#define FXDARRAY_UNLOCK_IF(pArray, pLockState, locked) { if ((locked) && (pArray)) FXDARRAY_UNLOCK((pArray), pLockState); }
+
+#define OVS_FXDARRAY_FOR_EACH(pArray, pCurItem, condition, code) \
+{                                                               \
+    ULONG countProcessed = 0;                                   \
+                                                                \
+    for (ULONG i = 0; i < OVS_MAX_ARRAY_SIZE; ++i)              \
+    {                                                           \
+        OVS_FXDARRAY_ITEM* pCurItem = (pArray)->array[i];        \
+                                                                \
+        if (pCurItem)                                           \
+        {                                                       \
+            LOCK_STATE_EX lockState = { 0 };                    \
+                                                                \
+            FXDITEM_LOCK_READ(pCurItem, &lockState);             \
+                                                                \
+            if ((condition))                                    \
+            {                                                   \
+                code;                                           \
+                                                                \
+                FXDITEM_UNLOCK(pCurItem, &lockState);            \
+                break;                                          \
+            }                                                   \
+                                                                \
+            FXDITEM_UNLOCK(pCurItem, &lockState);                \
+                                                                \
+            ++countProcessed;                                   \
+        }                                                       \
+                                                                \
+        if (countProcessed >= (pArray)->count)                  \
+        {                                                       \
+            break;                                              \
+        }                                                       \
+    }                                                           \
+                                                                \
+    OVS_CHECK(countProcessed == (pArray)->count);               \
+}
+
+/**********************************************************************************/
+
+//unsafe = you must lock with FXARRAY lock
+BOOLEAN FxdArray_FindNextFree_Unsafe(_In_ const OVS_FIXED_SIZED_ARRAY* pPorts, _Inout_ UINT16* pFirst);
+
+//unsafe = you must lock with FXARRAY lock
+OVS_ERROR FxdArray_AddByNumber_Unsafe(_Inout_ OVS_FIXED_SIZED_ARRAY* pArray, _In_ const OVS_FXDARRAY_ITEM* pItem, UINT16 number);
+
+//unsafe = you must lock with FXARRAY lock
+BOOLEAN FxdArray_Add_Unsafe(_Inout_ OVS_FIXED_SIZED_ARRAY* pArray, const OVS_FXDARRAY_ITEM* pItem, _Out_ UINT16* pNumber);
+
+_Ret_maybenull_
+OVS_FXDARRAY_ITEM* FxdArray_Find_Unsafe(_In_ const OVS_FIXED_SIZED_ARRAY* pArray, FxdArrayCondition condition, _In_ const VOID* pCondData);
+
+_Ret_maybenull_
+OVS_FXDARRAY_ITEM* FxdArray_Find_Ref(_In_ const OVS_FIXED_SIZED_ARRAY* pArray, FxdArrayCondition condition, _In_ const VOID* pCondData);
+
+_Ret_maybenull_
+BOOLEAN FxdArray_Remove_Unsafe(_Inout_ OVS_FIXED_SIZED_ARRAY* pArray, _In_ OVS_FXDARRAY_ITEM* pItem, UINT16 number);
diff --git a/datapath-windows/ovsext/ovsext.vcxproj b/datapath-windows/ovsext/ovsext.vcxproj
index 99aa6f6..2c62cab 100644
--- a/datapath-windows/ovsext/ovsext.vcxproj
+++ b/datapath-windows/ovsext/ovsext.vcxproj
@@ -72,6 +72,7 @@
   <ItemGroup Label="WrappedTaskItems">
     <ClInclude Include="Core\Debug.h" />
     <ClInclude Include="Core\Error.h" />
+    <ClInclude Include="Core\FixedSizedArray.h" />
     <ClInclude Include="Core\IpHelper.h" />
     <ClInclude Include="Core\Jhash.h" />
     <ClInclude Include="Core\List.h" />
@@ -136,6 +137,7 @@
   <ItemGroup>
     <ClCompile Include="Core\Debug.c" />
     <ClCompile Include="Core\Driver.c" />
+    <ClCompile Include="Core\FixedSizedArray.c" />
     <ClCompile Include="Core\IpHelper.c" />
     <ClCompile Include="Core\Jhash.c" />
     <ClCompile Include="Core\SpookyHash.c" />
diff --git a/datapath-windows/ovsext/ovsext.vcxproj.filters b/datapath-windows/ovsext/ovsext.vcxproj.filters
index fc3ba3b..96cfac6 100644
--- a/datapath-windows/ovsext/ovsext.vcxproj.filters
+++ b/datapath-windows/ovsext/ovsext.vcxproj.filters
@@ -86,6 +86,9 @@
     <ClInclude Include="Core\RefCount.h">
       <Filter>Core</Filter>
     </ClInclude>
+    <ClInclude Include="Core\FixedSizedArray.h">
+      <Filter>Core</Filter>
+    </ClInclude>
   </ItemGroup>
   <ItemGroup>
     <ResourceCompile Include="ovsext.rc" />
@@ -178,5 +181,8 @@
     <ClCompile Include="Core\SpookyHash.c">
       <Filter>Core</Filter>
     </ClCompile>
+    <ClCompile Include="Core\FixedSizedArray.c">
+      <Filter>Core</Filter>
+    </ClCompile>
   </ItemGroup>
-</Project>
\ No newline at end of file
+</Project>
diff --git a/datapath-windows/ovsext/precomp.h b/datapath-windows/ovsext/precomp.h
index 529d7de..3fd5da2 100644
--- a/datapath-windows/ovsext/precomp.h
+++ b/datapath-windows/ovsext/precomp.h
@@ -24,4 +24,5 @@
 #include "Core/Debug.h"
 #include "Core/Types.h"
 #include "Core/Util.h"
+#include "Core/RefCount.h"
 #include "OpenFlow/Pub.h"
--
1.8.3.msysgit.0





More information about the dev mailing list