[ovs-dev] [PATCH] datapath-windows: Add FixedSizedArray
Samuel Ghinet
sghinet at cloudbasesolutions.com
Wed Aug 6 14:36:52 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