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 <sghi...@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 _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev