summaryrefslogtreecommitdiffstats
path: root/include/iprt/cpp/hardavlslaballocator.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/iprt/cpp/hardavlslaballocator.h')
-rw-r--r--include/iprt/cpp/hardavlslaballocator.h218
1 files changed, 218 insertions, 0 deletions
diff --git a/include/iprt/cpp/hardavlslaballocator.h b/include/iprt/cpp/hardavlslaballocator.h
new file mode 100644
index 00000000..515782b5
--- /dev/null
+++ b/include/iprt/cpp/hardavlslaballocator.h
@@ -0,0 +1,218 @@
+/** @file
+ * IPRT - Hardened AVL tree slab allocator.
+ */
+
+/*
+ * Copyright (C) 2022 Oracle and/or its affiliates.
+ *
+ * This file is part of VirtualBox base platform packages, as
+ * available from https://www.virtualbox.org.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation, in version 3 of the
+ * License.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <https://www.gnu.org/licenses>.
+ *
+ * The contents of this file may alternatively be used under the terms
+ * of the Common Development and Distribution License Version 1.0
+ * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
+ * in the VirtualBox distribution, in which case the provisions of the
+ * CDDL are applicable instead of those of the GPL.
+ *
+ * You may elect to license modified versions of this file under the
+ * terms and conditions of either the GPL or the CDDL or both.
+ *
+ * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
+ */
+
+#ifndef IPRT_INCLUDED_cpp_hardavlslaballocator_h
+#define IPRT_INCLUDED_cpp_hardavlslaballocator_h
+#ifndef RT_WITHOUT_PRAGMA_ONCE
+# pragma once
+#endif
+
+#include <iprt/asm.h>
+#include <iprt/assert.h>
+#include <iprt/err.h>
+#include <iprt/string.h>
+
+/** @addtogroup grp_rt_cpp_hardavl
+ * @{
+ */
+
+
+/**
+ * Slab allocator for the hardened AVL tree.
+ */
+template<typename NodeType>
+struct RTCHardAvlTreeSlabAllocator
+{
+ /** Pointer to an array of nodes. */
+ NodeType *m_paNodes;
+ /** Node allocation bitmap: 1 = free, 0 = allocated. */
+ uint64_t *m_pbmAlloc;
+ /** Max number of nodes in m_paNodes and valid bits in m_pbmAlloc. */
+ uint32_t m_cNodes;
+ /** Pointer error counter. */
+ uint32_t m_cErrors;
+ /** Allocation hint. */
+ uint32_t m_idxAllocHint;
+ uint32_t m_uPadding;
+
+ enum
+ {
+ kNilIndex = 0,
+ kErr_IndexOutOfBound = -1,
+ kErr_PointerOutOfBound = -2,
+ kErr_MisalignedPointer = -3,
+ kErr_NodeIsFree = -4,
+ kErr_Last = kErr_NodeIsFree
+ };
+
+ RTCHardAvlTreeSlabAllocator() RT_NOEXCEPT
+ : m_paNodes(NULL)
+ , m_pbmAlloc(NULL)
+ , m_cNodes(0)
+ , m_cErrors(0)
+ , m_idxAllocHint(0)
+ , m_uPadding(0)
+ {}
+
+ inline void initSlabAllocator(uint32_t a_cNodes, NodeType *a_paNodes, uint64_t *a_pbmAlloc) RT_NOEXCEPT
+ {
+ m_cNodes = a_cNodes;
+ m_paNodes = a_paNodes;
+ m_pbmAlloc = a_pbmAlloc;
+
+ /* Initialize the allocation bit. */
+ RT_BZERO(a_pbmAlloc, (a_cNodes + 63) / 64 * 8);
+ ASMBitSetRange(a_pbmAlloc, 0, a_cNodes);
+ }
+
+ inline NodeType *ptrFromInt(uint32_t a_idxNode1) RT_NOEXCEPT
+ {
+ if (a_idxNode1 == (uint32_t)kNilIndex)
+ return NULL;
+ AssertMsgReturnStmt(a_idxNode1 <= m_cNodes, ("a_idxNode1=%#x m_cNodes=%#x\n", a_idxNode1, m_cNodes),
+ m_cErrors++, (NodeType *)(intptr_t)kErr_IndexOutOfBound);
+ AssertMsgReturnStmt(ASMBitTest(m_pbmAlloc, a_idxNode1 - 1) == false, ("a_idxNode1=%#x\n", a_idxNode1),
+ m_cErrors++, (NodeType *)(intptr_t)kErr_NodeIsFree);
+ return &m_paNodes[a_idxNode1 - 1];
+ }
+
+ static inline bool isPtrRetOkay(NodeType *a_pNode) RT_NOEXCEPT
+ {
+ return (uintptr_t)a_pNode < (uintptr_t)kErr_Last;
+ }
+
+ static inline int ptrErrToStatus(NodeType *a_pNode) RT_NOEXCEPT
+ {
+ return (int)(intptr_t)a_pNode - (VERR_HARDAVL_INDEX_OUT_OF_BOUNDS - kErr_IndexOutOfBound);
+ }
+
+ inline uint32_t ptrToInt(NodeType *a_pNode) RT_NOEXCEPT
+ {
+ if (a_pNode == NULL)
+ return 0;
+ uintptr_t const offNode = (uintptr_t)a_pNode - (uintptr_t)m_paNodes;
+ uintptr_t const idxNode0 = offNode / sizeof(m_paNodes[0]);
+ AssertMsgReturnStmt((offNode % sizeof(m_paNodes[0])) == 0,
+ ("pNode=%p / offNode=%#zx vs m_paNodes=%p L %#x, each %#x bytes\n",
+ a_pNode, offNode, m_paNodes, m_cNodes, sizeof(m_paNodes[0])),
+ m_cErrors++, (uint32_t)kErr_MisalignedPointer);
+ AssertMsgReturnStmt(idxNode0 < m_cNodes,
+ ("pNode=%p vs m_paNodes=%p L %#x\n", a_pNode, m_paNodes, m_cNodes),
+ m_cErrors++, (uint32_t)kErr_PointerOutOfBound);
+ AssertMsgReturnStmt(ASMBitTest(m_pbmAlloc, idxNode0) == false, ("a_pNode=%p idxNode0=%#x\n", a_pNode, idxNode0),
+ m_cErrors++, (uint32_t)kErr_NodeIsFree);
+ return idxNode0 + 1;
+ }
+
+ static inline bool isIdxRetOkay(uint32_t a_idxNode) RT_NOEXCEPT
+ {
+ return a_idxNode < (uint32_t)kErr_Last;
+ }
+
+ static inline int idxErrToStatus(uint32_t a_idxNode) RT_NOEXCEPT
+ {
+ return (int)a_idxNode - (VERR_HARDAVL_INDEX_OUT_OF_BOUNDS - kErr_IndexOutOfBound);
+ }
+
+ inline bool isIntValid(uint32_t a_idxNode1) RT_NOEXCEPT
+ {
+ return a_idxNode1 <= m_cNodes;
+ }
+
+ inline int freeNode(NodeType *a_pNode) RT_NOEXCEPT
+ {
+ uint32_t idxNode1 = ptrToInt(a_pNode);
+ if (idxNode1 == (uint32_t)kNilIndex)
+ return 0;
+ if (idxNode1 < (uint32_t)kErr_Last)
+ {
+ AssertMsgReturnStmt(ASMAtomicBitTestAndSet(m_pbmAlloc, idxNode1 - 1) == false,
+ ("a_pNode=%p idxNode1=%#x\n", a_pNode, idxNode1),
+ m_cErrors++, kErr_NodeIsFree);
+ return 0;
+ }
+ return (int)idxNode1;
+ }
+
+ inline NodeType *allocateNode(void) RT_NOEXCEPT
+ {
+ /*
+ * Use the hint first, then scan the whole bitmap.
+ * Note! We don't expect concurrent allocation calls, so no need to repeat.
+ */
+ uint32_t const idxHint = m_idxAllocHint;
+ uint32_t idxNode0;
+ if ( idxHint >= m_cNodes
+ || (int32_t)(idxNode0 = (uint32_t)ASMBitNextSet(m_pbmAlloc, m_cNodes, idxHint)) < 0)
+ idxNode0 = (uint32_t)ASMBitFirstSet(m_pbmAlloc, m_cNodes);
+ if ((int32_t)idxNode0 >= 0)
+ {
+ if (ASMAtomicBitTestAndClear(m_pbmAlloc, idxNode0) == true)
+ {
+ m_idxAllocHint = idxNode0;
+ return &m_paNodes[idxNode0];
+ }
+ AssertMsgFailed(("idxNode0=%#x\n", idxNode0));
+ m_cErrors++;
+ }
+ return NULL;
+ }
+};
+
+
+/**
+ * Placeholder structure for ring-3 slab allocator.
+ */
+typedef struct RTCHardAvlTreeSlabAllocatorR3_T
+{
+ /** Pointer to an array of nodes. */
+ RTR3PTR m_paNodes;
+ /** Node allocation bitmap: 1 = free, 0 = allocated. */
+ RTR3PTR m_pbmAlloc;
+ /** Max number of nodes in m_paNodes and valid bits in m_pbmAlloc. */
+ uint32_t m_cNodes;
+ /** Pointer error counter. */
+ uint32_t m_cErrors;
+ /** Allocation hint. */
+ uint32_t m_idxAllocHint;
+ uint32_t m_uPadding;
+} RTCHardAvlTreeSlabAllocatorR3_T;
+AssertCompileSize(RTCHardAvlTreeSlabAllocatorR3_T,
+ sizeof(RTCHardAvlTreeSlabAllocator<RTUINT128U>) - (sizeof(void *) - sizeof(RTR3PTR)) * 2);
+
+/** @} */
+
+#endif /* !IPRT_INCLUDED_cpp_hardavlslaballocator_h */
+