1  /** @file


2  * IPRT  Heap Implementations


3  */


4 


5  /*


6  * Copyright (C) 20062023 Oracle and/or its affiliates.


7  *


8  * This file is part of VirtualBox base platform packages, as


9  * available from https://www.virtualbox.org.


10  *


11  * This program is free software; you can redistribute it and/or


12  * modify it under the terms of the GNU General Public License


13  * as published by the Free Software Foundation, in version 3 of the


14  * License.


15  *


16  * This program is distributed in the hope that it will be useful, but


17  * WITHOUT ANY WARRANTY; without even the implied warranty of


18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU


19  * General Public License for more details.


20  *


21  * You should have received a copy of the GNU General Public License


22  * along with this program; if not, see <https://www.gnu.org/licenses>.


23  *


24  * The contents of this file may alternatively be used under the terms


25  * of the Common Development and Distribution License Version 1.0


26  * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included


27  * in the VirtualBox distribution, in which case the provisions of the


28  * CDDL are applicable instead of those of the GPL.


29  *


30  * You may elect to license modified versions of this file under the


31  * terms and conditions of either the GPL or the CDDL or both.


32  *


33  * SPDXLicenseIdentifier: GPL3.0only OR CDDL1.0


34  */


35 


36  #ifndef IPRT_INCLUDED_heap_h


37  #define IPRT_INCLUDED_heap_h


38  #ifndef RT_WITHOUT_PRAGMA_ONCE


39  # pragma once


40  #endif


41 


42  #include <iprt/cdefs.h>


43  #include <iprt/types.h>


44 


45  RT_C_DECLS_BEGIN


46 


47  /** @defgroup grp_rt_heap RTHeap  Heap Implementations


48  * @ingroup grp_rt


49  * @{


50  */


51 


52 


53  /** @defgroup grp_rt_heap_simple RTHeapSimple  Simple Heap


54  * @{


55  */


56 


57  /**


58  * Initializes the heap.


59  *


60  * @returns IPRT status code.


61  * @param pHeap Where to store the heap anchor block on success.


62  * @param pvMemory Pointer to the heap memory.


63  * @param cbMemory The size of the heap memory.


64  */


65  RTDECL(int) RTHeapSimpleInit(PRTHEAPSIMPLE pHeap, void *pvMemory, size_t cbMemory);


66 


67  /**


68  * Merge two simple heaps into one.


69  *


70  * The requirement is of course that they next two each other memory wise.


71  *


72  * @returns IPRT status code.


73  * @param pHeap Where to store the handle to the merged heap on success.


74  * @param Heap1 Handle to the first heap.


75  * @param Heap2 Handle to the second heap.


76  * @remark This API isn't implemented yet.


77  */


78  RTDECL(int) RTHeapSimpleMerge(PRTHEAPSIMPLE pHeap, RTHEAPSIMPLE Heap1, RTHEAPSIMPLE Heap2);


79 


80  /**


81  * Relocater the heap internal structures after copying it to a new location.


82  *


83  * This can be used when loading a saved heap.


84  *


85  * @returns IPRT status code.


86  * @param hHeap Heap handle that has already been adjusted by to the new


87  * location. That is to say, when calling


88  * RTHeapSimpleInit, the caller must note the offset of the


89  * returned heap handle into the heap memory. This offset


90  * must be used when calcuating the handle value for the


91  * new location. The offset may in some cases not be zero!


92  * @param offDelta The delta between the new and old location, i.e. what


93  * should be added to the internal pointers.


94  */


95  RTDECL(int) RTHeapSimpleRelocate(RTHEAPSIMPLE hHeap, uintptr_t offDelta);


96 


97  /**


98  * Allocates memory from the specified simple heap.


99  *


100  * @returns Pointer to the allocated memory block on success.


101  * @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)


102  *


103  * @param Heap The heap to allocate the memory on.


104  * @param cb The requested heap block size.


105  * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.


106  * Must be a power of 2.


107  */


108  RTDECL(void *) RTHeapSimpleAlloc(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment);


109 


110  /**


111  * Allocates zeroed memory from the specified simple heap.


112  *


113  * @returns Pointer to the allocated memory block on success.


114  * @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)


115  *


116  * @param Heap The heap to allocate the memory on.


117  * @param cb The requested heap block size.


118  * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.


119  * Must be a power of 2.


120  */


121  RTDECL(void *) RTHeapSimpleAllocZ(RTHEAPSIMPLE Heap, size_t cb, size_t cbAlignment);


122 


123  /**


124  * Reallocates / Allocates / Frees a heap block.


125  *


126  * @param Heap The heap. This is optional and will only be used for strict assertions.


127  * @param pv The heap block returned by RTHeapSimple. If NULL it behaves like RTHeapSimpleAlloc().


128  * @param cbNew The new size of the heap block. If NULL it behaves like RTHeapSimpleFree().


129  * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.


130  * Must be a power of 2.


131  * @remark This API isn't implemented yet.


132  */


133  RTDECL(void *) RTHeapSimpleRealloc(RTHEAPSIMPLE Heap, void *pv, size_t cbNew, size_t cbAlignment);


134 


135  /**


136  * Reallocates / Allocates / Frees a heap block, zeroing any new bits.


137  *


138  * @param Heap The heap. This is optional and will only be used for strict assertions.


139  * @param pv The heap block returned by RTHeapSimple. If NULL it behaves like RTHeapSimpleAllocZ().


140  * @param cbNew The new size of the heap block. If NULL it behaves like RTHeapSimpleFree().


141  * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.


142  * Must be a power of 2.


143  * @remark This API isn't implemented yet.


144  */


145  RTDECL(void *) RTHeapSimpleReallocZ(RTHEAPSIMPLE Heap, void *pv, size_t cbNew, size_t cbAlignment);


146 


147  /**


148  * Frees memory allocated from a simple heap.


149  *


150  * @param Heap The heap. This is optional and will only be used for strict assertions.


151  * @param pv The heap block returned by RTHeapSimple


152  */


153  RTDECL(void) RTHeapSimpleFree(RTHEAPSIMPLE Heap, void *pv);


154 


155  /**


156  * Gets the size of the specified heap block.


157  *


158  * @returns The actual size of the heap block.


159  * @returns 0 if \a pv is NULL or it doesn't point to a valid heap block. An invalid \a pv


160  * can also cause traps or trigger assertions.


161  * @param Heap The heap. This is optional and will only be used for strict assertions.


162  * @param pv The heap block returned by RTHeapSimple


163  */


164  RTDECL(size_t) RTHeapSimpleSize(RTHEAPSIMPLE Heap, void *pv);


165 


166  /**


167  * Gets the size of the heap.


168  *


169  * This size includes all the internal heap structures. So, even if the heap is


170  * empty the RTHeapSimpleGetFreeSize() will never reach the heap size returned


171  * by this function.


172  *


173  * @returns The heap size.


174  * @returns 0 if heap was safely detected as being bad.


175  * @param Heap The heap.


176  */


177  RTDECL(size_t) RTHeapSimpleGetHeapSize(RTHEAPSIMPLE Heap);


178 


179  /**


180  * Returns the sum of all free heap blocks.


181  *


182  * This is the amount of memory you can theoretically allocate


183  * if you do allocations exactly matching the free blocks.


184  *


185  * @returns The size of the free blocks.


186  * @returns 0 if heap was safely detected as being bad.


187  * @param Heap The heap.


188  */


189  RTDECL(size_t) RTHeapSimpleGetFreeSize(RTHEAPSIMPLE Heap);


190 


191  /**


192  * Printf like callbaclk function for RTHeapSimpleDump.


193  * @param pszFormat IPRT format string.


194  * @param ... Format arguments.


195  */


196  typedef DECLCALLBACKTYPE(void, FNRTHEAPSIMPLEPRINTF,(const char *pszFormat, ...)) RT_IPRT_FORMAT_ATTR(1, 2);


197  /** Pointer to a FNRTHEAPSIMPLEPRINTF function. */


198  typedef FNRTHEAPSIMPLEPRINTF *PFNRTHEAPSIMPLEPRINTF;


199 


200  /**


201  * Dumps the hypervisor heap.


202  *


203  * @param Heap The heap handle.


204  * @param pfnPrintf Printf like function that groks IPRT formatting.


205  */


206  RTDECL(void) RTHeapSimpleDump(RTHEAPSIMPLE Heap, PFNRTHEAPSIMPLEPRINTF pfnPrintf);


207 


208  /** @} */


209 


210 


211 


212  /** @defgroup grp_rt_heap_offset RTHeapOffset  Offset Based Heap


213  *


214  * This is a variation on the simple heap that doesn't use pointers internally


215  * and therefore can be saved and restored without any extra effort.


216  *


217  * @{


218  */


219 


220  /**


221  * Initializes the heap.


222  *


223  * @returns IPRT status code.


224  * @param phHeap Where to store the heap anchor block on success.


225  * @param pvMemory Pointer to the heap memory.


226  * @param cbMemory The size of the heap memory.


227  */


228  RTDECL(int) RTHeapOffsetInit(PRTHEAPOFFSET phHeap, void *pvMemory, size_t cbMemory);


229 


230  /**


231  * Merge two simple heaps into one.


232  *


233  * The requirement is of course that they next two each other memory wise.


234  *


235  * @returns IPRT status code.


236  * @param phHeap Where to store the handle to the merged heap on success.


237  * @param hHeap1 Handle to the first heap.


238  * @param hHeap2 Handle to the second heap.


239  * @remark This API isn't implemented yet.


240  */


241  RTDECL(int) RTHeapOffsetMerge(PRTHEAPOFFSET phHeap, RTHEAPOFFSET hHeap1, RTHEAPOFFSET hHeap2);


242 


243  /**


244  * Allocates memory from the specified simple heap.


245  *


246  * @returns Pointer to the allocated memory block on success.


247  * @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)


248  *


249  * @param hHeap The heap to allocate the memory on.


250  * @param cb The requested heap block size.


251  * @param cbAlignment The requested heap block alignment. Pass 0 for default alignment.


252  * Must be a power of 2.


253  */


254  RTDECL(void *) RTHeapOffsetAlloc(RTHEAPOFFSET hHeap, size_t cb, size_t cbAlignment);


255 


256  /**


257  * Allocates zeroed memory from the specified simple heap.


258  *


259  * @returns Pointer to the allocated memory block on success.


260  * @returns NULL if the request cannot be satisfied. (A VERR_NO_MEMORY condition.)


261  *


262  * @param hHeap The heap to allocate the memory on.


263  * @param cb The requested heap block size.


264  * @param cbAlignment The requested heap block alignment. Pass 0 for default


265  * alignment. Must be a power of 2.


266  */


267  RTDECL(void *) RTHeapOffsetAllocZ(RTHEAPOFFSET hHeap, size_t cb, size_t cbAlignment);


268 


269  /**


270  * Reallocates / Allocates / Frees a heap block.


271  *


272  * @param hHeap The heap handle. This is optional and will only be used


273  * for strict assertions.


274  * @param pv The heap block returned by RTHeapOffset. If NULL it


275  * behaves like RTHeapOffsetAlloc().


276  * @param cbNew The new size of the heap block. If NULL it behaves like


277  * RTHeapOffsetFree().


278  * @param cbAlignment The requested heap block alignment. Pass 0 for default


279  * alignment. Must be a power of 2.


280  * @remark This API isn't implemented yet.


281  */


282  RTDECL(void *) RTHeapOffsetRealloc(RTHEAPOFFSET hHeap, void *pv, size_t cbNew, size_t cbAlignment);


283 


284  /**


285  * Reallocates / Allocates / Frees a heap block, zeroing any new bits.


286  *


287  * @param hHeap The heap handle. This is optional and will only be used


288  * for strict assertions.


289  * @param pv The heap block returned by RTHeapOffset. If NULL it


290  * behaves like RTHeapOffsetAllocZ().


291  * @param cbNew The new size of the heap block. If NULL it behaves like


292  * RTHeapOffsetFree().


293  * @param cbAlignment The requested heap block alignment. Pass 0 for default


294  * alignment. Must be a power of 2.


295  * @remark This API isn't implemented yet.


296  */


297  RTDECL(void *) RTHeapOffsetReallocZ(RTHEAPOFFSET hHeap, void *pv, size_t cbNew, size_t cbAlignment);


298 


299  /**


300  * Frees memory allocated from a simple heap.


301  *


302  * @param hHeap The heap handle. This is optional and will only be used


303  * for strict assertions.


304  * @param pv The heap block returned by RTHeapOffset


305  */


306  RTDECL(void) RTHeapOffsetFree(RTHEAPOFFSET hHeap, void *pv);


307 


308  /**


309  * Gets the size of the specified heap block.


310  *


311  * @returns The actual size of the heap block.


312  * @returns 0 if \a pv is NULL or it doesn't point to a valid heap block. An


313  * invalid \a pv can also cause traps or trigger assertions.


314  *


315  * @param hHeap The heap handle. This is optional and will only be used


316  * for strict assertions.


317  * @param pv The heap block returned by RTHeapOffset


318  */


319  RTDECL(size_t) RTHeapOffsetSize(RTHEAPOFFSET hHeap, void *pv);


320 


321  /**


322  * Gets the size of the heap.


323  *


324  * This size includes all the internal heap structures. So, even if the heap is


325  * empty the RTHeapOffsetGetFreeSize() will never reach the heap size returned


326  * by this function.


327  *


328  * @returns The heap size.


329  * @returns 0 if heap was safely detected as being bad.


330  * @param hHeap The heap handle.


331  */


332  RTDECL(size_t) RTHeapOffsetGetHeapSize(RTHEAPOFFSET hHeap);


333 


334  /**


335  * Returns the sum of all free heap blocks.


336  *


337  * This is the amount of memory you can theoretically allocate


338  * if you do allocations exactly matching the free blocks.


339  *


340  * @returns The size of the free blocks.


341  * @returns 0 if heap was safely detected as being bad.


342  * @param hHeap The heap handle.


343  */


344  RTDECL(size_t) RTHeapOffsetGetFreeSize(RTHEAPOFFSET hHeap);


345 


346  /**


347  * Printf like callbaclk function for RTHeapOffsetDump.


348  * @param pszFormat IPRT format string.


349  * @param ... Format arguments.


350  */


351  typedef DECLCALLBACKTYPE(void, FNRTHEAPOFFSETPRINTF,(const char *pszFormat, ...)) RT_IPRT_FORMAT_ATTR(1, 2);


352  /** Pointer to a FNRTHEAPOFFSETPRINTF function. */


353  typedef FNRTHEAPOFFSETPRINTF *PFNRTHEAPOFFSETPRINTF;


354 


355  /**


356  * Dumps the hypervisor heap.


357  *


358  * @param hHeap The heap handle.


359  * @param pfnPrintf Printf like function that groks IPRT formatting.


360  */


361  RTDECL(void) RTHeapOffsetDump(RTHEAPOFFSET hHeap, PFNRTHEAPOFFSETPRINTF pfnPrintf);


362 


363  /** @} */


364 


365  /** @} */


366  RT_C_DECLS_END


367 


368  #endif /* !IPRT_INCLUDED_heap_h */


369 

