handletable.cpp revision 4d0b8f024a4654c1f61c8c4b7e16320719f7fea4
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * IPRT - Handle Tables.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * Copyright (C) 2008 Sun Microsystems, Inc.
df03c5ed15c9b5bf6d75fedcdf5057d3ffce8577vboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * available from http://www.virtualbox.org. This file is free software;
92a27575521748a392dcd1b996fce55b87411a00vboxsync * you can redistribute it and/or modify it under the terms of the GNU
92a27575521748a392dcd1b996fce55b87411a00vboxsync * General Public License (GPL) as published by the Free Software
92a27575521748a392dcd1b996fce55b87411a00vboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
92a27575521748a392dcd1b996fce55b87411a00vboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
92a27575521748a392dcd1b996fce55b87411a00vboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
92a27575521748a392dcd1b996fce55b87411a00vboxsync * The contents of this file may alternatively be used under the terms
92a27575521748a392dcd1b996fce55b87411a00vboxsync * of the Common Development and Distribution License Version 1.0
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * VirtualBox OSE distribution, in which case the provisions of the
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * CDDL are applicable instead of those of the GPL.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * You may elect to license modified versions of this file under the
10cdf5733351fdcd857d439ca32189e812f18682vboxsync * terms and conditions of either the GPL or the CDDL or both.
10cdf5733351fdcd857d439ca32189e812f18682vboxsync * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
10cdf5733351fdcd857d439ca32189e812f18682vboxsync * Clara, CA 95054 USA or visit http://www.sun.com if you need
10cdf5733351fdcd857d439ca32189e812f18682vboxsync * additional information or have any questions.
10cdf5733351fdcd857d439ca32189e812f18682vboxsync/*******************************************************************************
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync* Header Files *
10cdf5733351fdcd857d439ca32189e812f18682vboxsync*******************************************************************************/
10cdf5733351fdcd857d439ca32189e812f18682vboxsync/*******************************************************************************
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync* Defined Constants And Macros *
10cdf5733351fdcd857d439ca32189e812f18682vboxsync*******************************************************************************/
10cdf5733351fdcd857d439ca32189e812f18682vboxsync/** The number of entries in the 2nd level lookup table. */
10cdf5733351fdcd857d439ca32189e812f18682vboxsync/** The number of (max) 1st level entries requiring dynamic allocation of the
10cdf5733351fdcd857d439ca32189e812f18682vboxsync * 1st level table. If the max number is below this threshold, the 1st level
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * table will be allocated as part of the handle table structure. */
10cdf5733351fdcd857d439ca32189e812f18682vboxsync/** Checks whether a object pointer is really a free entry or not. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync#define RTHT_IS_FREE(pvObj) ( ((uintptr_t)(pvObj) & 3) == 3 )
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync/** Sets RTHTENTRYFREE::iNext. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync } while (0)
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync/** Gets the index part of RTHTENTRYFREE::iNext. */
cd9e4940318086a06a68bf301960563dcb72b939vboxsync#define RTHT_GET_FREE_IDX(pFree) ( (uint32_t)((pFree)->iNext >> 2) )
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync/** @def NIL_RTHT_INDEX
10cdf5733351fdcd857d439ca32189e812f18682vboxsync * The NIL handle index for use in the free list. (The difference between
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * 32-bit and 64-bit hosts here comes down to the shifting performed for
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * RTHTENTRYFREE::iNext.) */
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync/*******************************************************************************
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync* Structures and Typedefs *
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync*******************************************************************************/
4a429a59b1a82ce092626ea5f7512466c18f2015vboxsync * Handle table entry, simple variant.
4a429a59b1a82ce092626ea5f7512466c18f2015vboxsynctypedef struct RTHTENTRY
4a429a59b1a82ce092626ea5f7512466c18f2015vboxsync /** The object. */
4a429a59b1a82ce092626ea5f7512466c18f2015vboxsync/** Pointer to a handle table entry, simple variant. */
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync * Handle table entry, context variant.
23ee8310386e73ba6760fa30831a7964713d34b6vboxsynctypedef struct RTHTENTRYCTX
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync /** The context. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** The object. */
86abc60770f825f8c2ed4257675b50a08743b687vboxsync/** Pointer to a handle table entry, context variant. */
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync * Free handle table entry, shared by all variants.
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync /** The index of the next handle, special format.
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync * In order to distinguish free and used handle table entries we exploit
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync * the heap alignment and use the lower two bits to do this. Used entries
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync * will have these bits set to 0, while free entries will have tem set
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync * to 3. Use the RTHT_GET_FREE_IDX and RTHT_SET_FREE_IDX macros to access
360c39d88dfa26b17181b57ebafdb24c2a113c63vboxsync * this field. */
360c39d88dfa26b17181b57ebafdb24c2a113c63vboxsync/** Pointer to a free handle table entry. */
23ee8310386e73ba6760fa30831a7964713d34b6vboxsyncAssertCompile(sizeof(RTHTENTRYFREE) <= sizeof(RTHTENTRY));
02fb80eb0db13569db21d1ce5e0f3e0d5a6122aavboxsyncAssertCompile(sizeof(RTHTENTRYFREE) <= sizeof(RTHTENTRYCTX));
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync * Internal handle table structure.
6967517de4be849f55b0141d6089add0eff2aa7bvboxsync /** Magic value (RTHANDLETABLE_MAGIC). */
23ee8310386e73ba6760fa30831a7964713d34b6vboxsync /** The handle table flags specified to RTHandleTableCreateEx. */
7b213bb002950f9fcf809f605cc584fa543481advboxsync /** The base handle value (i.e. the first handle). */
7b213bb002950f9fcf809f605cc584fa543481advboxsync /** The current number of handles.
7b213bb002950f9fcf809f605cc584fa543481advboxsync * This indirectly gives the size of the first level lookup table. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** The spinlock handle (NIL if RTHANDLETABLE_FLAGS_LOCKED wasn't used). */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** The level one lookup table. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** The retainer callback. Can be NULL. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** The user argument to the retainer. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** The max number of handles. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** The number of handles currently allocated. (for optimizing destruction) */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** The current number of 1st level entries. */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** Head of the list of free handle entires (index). */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /** Tail of the list of free handle entires (index). */
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync/** Pointer to an handle table structure. */
8364ffb7e421fa1ec2bd282ab4c52ac718873d46vboxsync * Looks up a simple handle.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @returns Pointer to the handle table entry on success, NULL on failure.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param pThis The handle table structure.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param h The handle to look up.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsyncDECLINLINE(PRTHTENTRY) rtHandleTableLookupSimple(PRTHANDLETABLEINT pThis, uint32_t h)
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync PRTHTENTRY paTable = (PRTHTENTRY)pThis->papvLevel1[i / RTHT_LEVEL2_ENTRIES];
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * Looks up a context handle.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @returns Pointer to the handle table entry on success, NULL on failure.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param pThis The handle table structure.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param h The handle to look up.
c7a92d481aced08517570d43bf75e2a9f3a8aaeavboxsyncDECLINLINE(PRTHTENTRYCTX) rtHandleTableLookupWithCtx(PRTHANDLETABLEINT pThis, uint32_t h)
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync PRTHTENTRYCTX paTable = (PRTHTENTRYCTX)pThis->papvLevel1[i / RTHT_LEVEL2_ENTRIES];
08a80484275b5172ce23729ecccc934c6a92d201vboxsyncDECLINLINE(void) rtHandleTableLock(PRTHANDLETABLEINT pThis, PRTSPINLOCKTMP pTmp)
48f33dfd8f615d457106bf76ae2d09b8b9167c1avboxsyncDECLINLINE(void) rtHandleTableUnlock(PRTHANDLETABLEINT pThis, PRTSPINLOCKTMP pTmp)
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsyncRTDECL(int) RTHandleTableCreateEx(PRTHANDLETABLE phHandleTable, uint32_t fFlags, uint32_t uBase, uint32_t cMax,
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsyncRTDECL(int) RTHandleTableCreate(PRTHANDLETABLE phHandleTable)
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync return RTHandleTableCreateEx(phHandleTable, RTHANDLETABLE_FLAGS_LOCKED, 1, 65534, NULL, NULL);
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsyncRTDECL(int) RTHandleTableDestroy(RTHANDLETABLE hHandleTable, PFNRTHANDLETABLEDELETE pfnDelete, void *pvUser)
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync * Allocates a handle from the handle table.
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync * @returns IPRT status code, almost any.
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync * @retval VINF_SUCCESS on success.
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync * @retval VERR_NO_MEMORY if we failed to extend the handle table.
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync * @retval VERR_NO_MORE_HANDLES if we're out of handles.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param hHandleTable The handle to the handle table.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param pvObj The object to associate with the new handle.
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync * @param ph Where to return the handle on success.
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync * @remarks Do not call this if RTHANDLETABLE_FLAGS_CONTEXT was used during creation.
bc8beda7587b16cafe7de7bea19149de1bd4b498vboxsyncRTDECL(int) RTHandleTableAlloc(RTHANDLETABLE hHandleTable, void *pvObj, uint32_t *ph);
59e30364f54880dd846c263711a2506d1182b1b5vboxsync * Looks up a handle.
59e30364f54880dd846c263711a2506d1182b1b5vboxsync * @returns The object pointer on success. NULL on failure.
cc8517c11be66037a9873fa03f280e7742efed6dvboxsync * @param hHandleTable The handle to the handle table.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param h The handle to lookup.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @remarks Do not call this if RTHANDLETABLE_FLAGS_CONTEXT was used during creation.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsyncRTDECL(void *) RTHandleTableLookup(RTHANDLETABLE hHandleTable, uint32_t h);
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * Looks up and frees a handle.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @returns The object pointer on success. NULL on failure.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param hHandleTable The handle to the handle table.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @param h The handle to lookup.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * @remarks Do not call this if RTHANDLETABLE_FLAGS_CONTEXT was used during creation.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsyncRTDECL(void *) RTHandleTableFree(RTHANDLETABLE hHandleTable, uint32_t h);
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsyncRTDECL(int) RTHandleTableAllocWithCtx(RTHANDLETABLE hHandleTable, void *pvObj, void *pvCtx, uint32_t *ph)
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /* validate the input */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, VERR_INVALID_HANDLE);
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync AssertReturn(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT, VERR_INVALID_FUNCTION);
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync AssertReturn(RTHT_IS_FREE(pvObj), VERR_INVALID_PARAMETER);
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * Allocation loop.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * Try grab a free entry from the head of the free list.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync PRTHTENTRYFREE pFree = (PRTHTENTRYFREE)rtHandleTableLookupWithCtx(pThis, i + pThis->uBase);
3196a540aa11c41264b0e79857b879e4ab566f4bvboxsync pThis->iFreeTail = pThis->iFreeHead = NIL_RTHT_INDEX;
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * Setup the entry and return.
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync * Must expand the handle table, unless it's full.
efda5c4c4db213abd0692df0ea34a26f6230d59avboxsync * Do we have to expand the 1st level table too?
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync uint32_t const iLevel1 = pThis->cCur / RTHT_LEVEL2_ENTRIES;
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync /* leave the lock (never do fancy stuff from behind a spinlock). */
efda5c4c4db213abd0692df0ea34a26f6230d59avboxsync * Do the allocation(s).
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync papvLevel1 = (void **)RTMemAlloc(sizeof(void *) * cLevel1);
efda5c4c4db213abd0692df0ea34a26f6230d59avboxsync PRTHTENTRYCTX paTable = (PRTHTENTRYCTX)RTMemAlloc(sizeof(*paTable) * RTHT_LEVEL2_ENTRIES);
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync /* re-enter the lock. */
efda5c4c4db213abd0692df0ea34a26f6230d59avboxsync * Insert the new bits, but be a bit careful as someone might have
efda5c4c4db213abd0692df0ea34a26f6230d59avboxsync * raced us expanding the table.
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync /* Replace the 1st level table. */
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync memcpy(papvLevel1, pThis->papvLevel1, sizeof(void *) * pThis->cLevel1);
efda5c4c4db213abd0692df0ea34a26f6230d59avboxsync memset(&papvLevel1[pThis->cLevel1], 0, sizeof(void *) * (cLevel1 - pThis->cLevel1));
efda5c4c4db213abd0692df0ea34a26f6230d59avboxsync /* free the obsolete one (outside the lock of course) */
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync /* insert the table we allocated */
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync uint32_t iLevel1New = pThis->cCur / RTHT_LEVEL2_ENTRIES;
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync /* link all entries into a free list. */
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync for (uint32_t i = 0; i < RTHT_LEVEL2_ENTRIES - 1; i++)
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync RTHT_SET_FREE_IDX((PRTHTENTRYFREE)&paTable[i], i + 1);
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync RTHT_SET_FREE_IDX((PRTHTENTRYFREE)&paTable[RTHT_LEVEL2_ENTRIES - 1], NIL_RTHT_INDEX);
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync paTable[RTHT_LEVEL2_ENTRIES - 1].pvCtx = (void *)~(uintptr_t)7;
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync /* join the free list with the other. */
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync PRTHTENTRYFREE pPrev = (PRTHTENTRYFREE)rtHandleTableLookupWithCtx(pThis, pThis->iFreeTail);
1cc3bd5463294790ba54c78fde5313264185e50cvboxsync pThis->iFreeTail = pThis->cCur + RTHT_LEVEL2_ENTRIES - 1;
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /* free the table (raced someone, and we lost). */
48f33dfd8f615d457106bf76ae2d09b8b9167c1avboxsyncRTDECL(void *) RTHandleTableLookupWithCtx(RTHANDLETABLE hHandleTable, uint32_t h, void *pvCtx)
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /* validate the input */
48f33dfd8f615d457106bf76ae2d09b8b9167c1avboxsync PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
48f33dfd8f615d457106bf76ae2d09b8b9167c1avboxsync AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, NULL);
48f33dfd8f615d457106bf76ae2d09b8b9167c1avboxsync AssertReturn(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT, NULL);
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /* acquire the lock */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * Perform the lookup and retaining.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync PRTHTENTRYCTX pEntry = rtHandleTableLookupWithCtx(pThis, h);
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync int rc = pThis->pfnRetain(hHandleTable, pEntry->pvObj, pvCtx, pThis->pvRetainUser);
95d42763b8808d795c23148d7dbc00a3b7b40d6fvboxsync /* release the lock */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsyncRTDECL(void *) RTHandleTableFreeWithCtx(RTHANDLETABLE hHandleTable, uint32_t h, void *pvCtx)
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /* validate the input */
cd9e4940318086a06a68bf301960563dcb72b939vboxsync PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, NULL);
5857f4e58ce2ef50d7f0c450fe4897026f9a9c3dvboxsync AssertReturn(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT, NULL);
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /* acquire the lock */
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync * Perform the lookup and retaining.
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync PRTHTENTRYCTX pEntry = rtHandleTableLookupWithCtx(pThis, h);
2705a216ac12110a0813d671e230797c886b4788vboxsync int rc = pThis->pfnRetain(hHandleTable, pEntry->pvObj, pvCtx, pThis->pvRetainUser);
de86a09bf42f7e7d80a0a5acf1e8e99d445be1d3vboxsync * Link it into the free list.
2705a216ac12110a0813d671e230797c886b4788vboxsync PRTHTENTRYFREE pPrev = (PRTHTENTRYFREE)rtHandleTableLookupWithCtx(pThis, pThis->iFreeTail + pThis->uBase);
db3dbd0ed7eb69f804a8921fa23a1267ea01f46evboxsync /* release the lock */