/* $Id: memcache.cpp 76553 2019-01-01 01:45:53Z vboxsync $ */ /** @file * IPRT - Memory Object Allocation Cache. */ /* * Copyright (C) 2006-2019 Oracle Corporation * * This file is part of VirtualBox Open Source Edition (OSE), as * available from http://www.virtualbox.org. This file is free software; * you can redistribute it and/or modify it under the terms of the GNU * General Public License (GPL) as published by the Free Software * Foundation, in version 2 as it comes in the "COPYING" file of the * VirtualBox OSE distribution. VirtualBox OSE is distributed in the * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind. * * The contents of this file may alternatively be used under the terms * of the Common Development and Distribution License Version 1.0 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the * VirtualBox OSE 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. */ /********************************************************************************************************************************* * Header Files * *********************************************************************************************************************************/ #include #include "internal/iprt.h" #include #include #include #include #include #include #include "internal/magics.h" /********************************************************************************************************************************* * Structures and Typedefs * *********************************************************************************************************************************/ /** Pointer to a cache instance. */ typedef struct RTMEMCACHEINT *PRTMEMCACHEINT; /** Pointer to a cache page. */ typedef struct RTMEMCACHEPAGE *PRTMEMCACHEPAGE; /** * A free object. * * @remarks This only works if the objects don't have a constructor or * destructor and are big enough. */ typedef struct RTMEMCACHEFREEOBJ { /** Pointer to the next free object */ struct RTMEMCACHEFREEOBJ * volatile pNext; } RTMEMCACHEFREEOBJ; /** Pointer to a free object. */ typedef RTMEMCACHEFREEOBJ *PRTMEMCACHEFREEOBJ; /** * A cache page. * * This is a page of memory that we split up in to a bunch object sized chunks * and hand out to the cache users. The bitmap is updated in an atomic fashion * so that we don't have to take any locks when freeing or allocating memory. */ typedef struct RTMEMCACHEPAGE { /** Pointer to the cache owning this page. * This is used for validation purposes only. */ PRTMEMCACHEINT pCache; /** Pointer to the next page. * This is marked as volatile since we'll be adding new entries to the list * without taking any locks. */ PRTMEMCACHEPAGE volatile pNext; /** Bitmap tracking allocated blocks. */ void volatile *pbmAlloc; /** Bitmap tracking which blocks that has been thru the constructor. */ void volatile *pbmCtor; /** Pointer to the object array. */ uint8_t *pbObjects; /** The number of objects on this page. */ uint32_t cObjects; /** Padding to force cFree into the next cache line. (ASSUMES CL = 64) */ uint8_t abPadding[ARCH_BITS == 32 ? 64 - 6*4 : 64 - 5*8 - 4]; /** The number of free objects. */ int32_t volatile cFree; } RTMEMCACHEPAGE; AssertCompileMemberOffset(RTMEMCACHEPAGE, cFree, 64); /** * Memory object cache instance. */ typedef struct RTMEMCACHEINT { /** Magic value (RTMEMCACHE_MAGIC). */ uint32_t u32Magic; /** The object size. */ uint32_t cbObject; /** Object alignment. */ uint32_t cbAlignment; /** The per page object count. */ uint32_t cPerPage; /** Number of bits in the bitmap. * @remarks This is higher or equal to cPerPage and it is aligned such that * the search operation will be most efficient on x86/AMD64. */ uint32_t cBits; /** The maximum number of objects. */ uint32_t cMax; /** Whether to the use the free list or not. */ bool fUseFreeList; /** Head of the page list. */ PRTMEMCACHEPAGE pPageHead; /** Poiner to the insertion point in the page list. */ PRTMEMCACHEPAGE volatile *ppPageNext; /** Constructor callback. */ PFNMEMCACHECTOR pfnCtor; /** Destructor callback. */ PFNMEMCACHEDTOR pfnDtor; /** Callback argument. */ void *pvUser; /** Critical section serializing page allocation and similar. */ RTCRITSECT CritSect; /** The total object count. */ uint32_t volatile cTotal; /** The number of free objects. */ int32_t volatile cFree; /** This may point to a page with free entries. */ PRTMEMCACHEPAGE volatile pPageHint; /** Stack of free items. * These are marked as used in the allocation bitmaps. * * @todo This doesn't scale well when several threads are beating on the * cache. Also, it totally doesn't work when the objects are too * small. */ PRTMEMCACHEFREEOBJ volatile pFreeTop; } RTMEMCACHEINT; /********************************************************************************************************************************* * Internal Functions * *********************************************************************************************************************************/ static void rtMemCacheFreeList(RTMEMCACHEINT *pThis, PRTMEMCACHEFREEOBJ pHead); RTDECL(int) RTMemCacheCreate(PRTMEMCACHE phMemCache, size_t cbObject, size_t cbAlignment, uint32_t cMaxObjects, PFNMEMCACHECTOR pfnCtor, PFNMEMCACHEDTOR pfnDtor, void *pvUser, uint32_t fFlags) { AssertPtr(phMemCache); AssertPtrNull(pfnCtor); AssertPtrNull(pfnDtor); AssertReturn(!pfnDtor || pfnCtor, VERR_INVALID_PARAMETER); AssertReturn(cbObject > 0, VERR_INVALID_PARAMETER); AssertReturn(cbObject <= PAGE_SIZE / 8, VERR_INVALID_PARAMETER); AssertReturn(!fFlags, VERR_INVALID_PARAMETER); if (cbAlignment == 0) { if (cbObject <= 2) cbAlignment = cbObject; else if (cbObject <= 4) cbAlignment = 4; else if (cbObject <= 8) cbAlignment = 8; else if (cbObject <= 16) cbAlignment = 16; else if (cbObject <= 32) cbAlignment = 32; else cbAlignment = 64; } else { AssertReturn(!((cbAlignment - 1) & cbAlignment), VERR_NOT_POWER_OF_TWO); AssertReturn(cbAlignment <= 64, VERR_OUT_OF_RANGE); } /* * Allocate and initialize the instance memory. */ RTMEMCACHEINT *pThis = (RTMEMCACHEINT *)RTMemAlloc(sizeof(*pThis)); if (!pThis) return VERR_NO_MEMORY; int rc = RTCritSectInit(&pThis->CritSect); if (RT_FAILURE(rc)) { RTMemFree(pThis); return rc; } pThis->u32Magic = RTMEMCACHE_MAGIC; pThis->cbObject = (uint32_t)RT_ALIGN_Z(cbObject, cbAlignment); pThis->cbAlignment = (uint32_t)cbAlignment; pThis->cPerPage = (uint32_t)((PAGE_SIZE - RT_ALIGN_Z(sizeof(RTMEMCACHEPAGE), cbAlignment)) / pThis->cbObject); while ( RT_ALIGN_Z(sizeof(RTMEMCACHEPAGE), 8) + pThis->cPerPage * pThis->cbObject + RT_ALIGN(pThis->cPerPage, 64) / 8 * 2 > PAGE_SIZE) pThis->cPerPage--; pThis->cBits = RT_ALIGN(pThis->cPerPage, 64); pThis->cMax = cMaxObjects; pThis->fUseFreeList = cbObject >= sizeof(RTMEMCACHEFREEOBJ) && !pfnCtor && !pfnDtor; pThis->pPageHead = NULL; pThis->ppPageNext = &pThis->pPageHead; pThis->pfnCtor = pfnCtor; pThis->pfnDtor = pfnDtor; pThis->pvUser = pvUser; pThis->cTotal = 0; pThis->cFree = 0; pThis->pPageHint = NULL; pThis->pFreeTop = NULL; *phMemCache = pThis; return VINF_SUCCESS; } RTDECL(int) RTMemCacheDestroy(RTMEMCACHE hMemCache) { RTMEMCACHEINT *pThis = hMemCache; if (!pThis) return VINF_SUCCESS; AssertPtrReturn(pThis, VERR_INVALID_HANDLE); AssertReturn(pThis->u32Magic == RTMEMCACHE_MAGIC, VERR_INVALID_HANDLE); #if 0 /*def RT_STRICT - don't require eveything to be freed. Caches are very convenient for lazy cleanup. */ uint32_t cFree = pThis->cFree; for (PRTMEMCACHEFREEOBJ pFree = pThis->pFreeTop; pFree && cFree < pThis->cTotal + 5; pFree = pFree->pNext) cFree++; AssertMsg(cFree == pThis->cTotal, ("cFree=%u cTotal=%u\n", cFree, pThis->cTotal)); #endif /* * Destroy it. */ AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTMEMCACHE_MAGIC_DEAD, RTMEMCACHE_MAGIC), VERR_INVALID_HANDLE); RTCritSectDelete(&pThis->CritSect); while (pThis->pPageHead) { PRTMEMCACHEPAGE pPage = pThis->pPageHead; pThis->pPageHead = pPage->pNext; pPage->cFree = 0; if (pThis->pfnDtor) { uint32_t iObj = pPage->cObjects; while (iObj-- > 0) if (ASMBitTestAndClear(pPage->pbmCtor, iObj)) pThis->pfnDtor(hMemCache, pPage->pbObjects + iObj * pThis->cbObject, pThis->pvUser); } RTMemPageFree(pPage, PAGE_SIZE); } RTMemFree(pThis); return VINF_SUCCESS; } /** * Grows the cache. * * @returns IPRT status code. * @param pThis The memory cache instance. */ static int rtMemCacheGrow(RTMEMCACHEINT *pThis) { /* * Enter the critical section here to avoid allocation races leading to * wasted memory (++) and make it easier to link in the new page. */ RTCritSectEnter(&pThis->CritSect); int rc = VINF_SUCCESS; if (pThis->cFree < 0) { /* * Allocate and initialize the new page. * * We put the constructor bitmap at the lower end right after cFree. * We then push the object array to the end of the page and place the * allocation bitmap below it. The hope is to increase the chance that * the allocation bitmap is in a different cache line than cFree since * this increases performance markably when lots of threads are beating * on the cache. */ PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)RTMemPageAlloc(PAGE_SIZE); if (pPage) { uint32_t const cObjects = RT_MIN(pThis->cPerPage, pThis->cMax - pThis->cTotal); ASMMemZeroPage(pPage); pPage->pCache = pThis; pPage->pNext = NULL; pPage->cFree = cObjects; pPage->cObjects = cObjects; uint8_t *pb = (uint8_t *)(pPage + 1); pb = RT_ALIGN_PT(pb, 8, uint8_t *); pPage->pbmCtor = pb; pb = (uint8_t *)pPage + PAGE_SIZE - pThis->cbObject * cObjects; pPage->pbObjects = pb; Assert(RT_ALIGN_P(pb, pThis->cbAlignment) == pb); pb -= pThis->cBits / 8; pb = (uint8_t *)((uintptr_t)pb & ~(uintptr_t)7); pPage->pbmAlloc = pb; Assert((uintptr_t)pPage->pbmCtor + pThis->cBits / 8 <= (uintptr_t)pPage->pbmAlloc); /* Mark the bitmap padding and any unused objects as allocated. */ for (uint32_t iBit = cObjects; iBit < pThis->cBits; iBit++) ASMBitSet(pPage->pbmAlloc, iBit); /* Make it the hint. */ ASMAtomicWritePtr(&pThis->pPageHint, pPage); /* Link the page in at the end of the list. */ ASMAtomicWritePtr(pThis->ppPageNext, pPage); pThis->ppPageNext = &pPage->pNext; /* Add it to the page counts. */ ASMAtomicAddS32(&pThis->cFree, cObjects); ASMAtomicAddU32(&pThis->cTotal, cObjects); } else rc = VERR_NO_MEMORY; } RTCritSectLeave(&pThis->CritSect); return rc; } /** * Grabs a an object in a page. * @returns New cFree value on success (0 or higher), -1 on failure. * @param pPage Pointer to the page. */ DECL_FORCE_INLINE(int32_t) rtMemCacheGrabObj(PRTMEMCACHEPAGE pPage) { if (ASMAtomicUoReadS32(&pPage->cFree) > 0) { int32_t cFreeNew = ASMAtomicDecS32(&pPage->cFree); if (cFreeNew >= 0) return cFreeNew; ASMAtomicIncS32(&pPage->cFree); } return -1; } RTDECL(int) RTMemCacheAllocEx(RTMEMCACHE hMemCache, void **ppvObj) { RTMEMCACHEINT *pThis = hMemCache; AssertPtrReturn(pThis, VERR_INVALID_PARAMETER); AssertReturn(pThis->u32Magic == RTMEMCACHE_MAGIC, VERR_INVALID_PARAMETER); /* * Try grab a free object from the stack. */ PRTMEMCACHEFREEOBJ pObj = ASMAtomicUoReadPtrT(&pThis->pFreeTop, PRTMEMCACHEFREEOBJ); if (pObj) { pObj = ASMAtomicXchgPtrT(&pThis->pFreeTop, NULL, PRTMEMCACHEFREEOBJ); if (pObj) { if (pObj->pNext) { Assert(pObj->pNext != pObj); PRTMEMCACHEFREEOBJ pAllocRace = ASMAtomicXchgPtrT(&pThis->pFreeTop, pObj->pNext, PRTMEMCACHEFREEOBJ); if (pAllocRace) rtMemCacheFreeList(pThis, pAllocRace); } pObj->pNext = NULL; *ppvObj = pObj; return VINF_SUCCESS; } } /* * Try grab a free object at the cache level. */ int32_t cNewFree = ASMAtomicDecS32(&pThis->cFree); if (RT_LIKELY(cNewFree < 0)) { uint32_t cTotal = ASMAtomicUoReadU32(&pThis->cTotal); if ( (uint32_t)(cTotal + -cNewFree) > pThis->cMax || (uint32_t)(cTotal + -cNewFree) <= cTotal) { ASMAtomicIncS32(&pThis->cFree); return VERR_MEM_CACHE_MAX_SIZE; } int rc = rtMemCacheGrow(pThis); if (RT_FAILURE(rc)) { ASMAtomicIncS32(&pThis->cFree); return rc; } } /* * Grab a free object at the page level. */ PRTMEMCACHEPAGE pPage = ASMAtomicUoReadPtrT(&pThis->pPageHint, PRTMEMCACHEPAGE); int32_t iObj = pPage ? rtMemCacheGrabObj(pPage) : -1; if (iObj < 0) { for (unsigned cLoops = 0; ; cLoops++) { for (pPage = pThis->pPageHead; pPage; pPage = pPage->pNext) { iObj = rtMemCacheGrabObj(pPage); if (iObj >= 0) { if (iObj > 0) ASMAtomicWritePtr(&pThis->pPageHint, pPage); break; } } if (iObj >= 0) break; Assert(cLoops != 2); Assert(cLoops < 10); } } Assert(iObj >= 0); Assert((uint32_t)iObj < pThis->cMax); /* * Find a free object in the allocation bitmap. Use the new cFree count * as a hint. */ if (ASMAtomicBitTestAndSet(pPage->pbmAlloc, iObj)) { for (unsigned cLoops2 = 0;; cLoops2++) { iObj = ASMBitFirstClear(pPage->pbmAlloc, pThis->cBits); if (RT_LIKELY(iObj >= 0)) { if (!ASMAtomicBitTestAndSet(pPage->pbmAlloc, iObj)) break; } else ASMMemoryFence(); Assert(cLoops2 != 40); } Assert(iObj >= 0); } void *pvObj = &pPage->pbObjects[iObj * pThis->cbObject]; Assert((uintptr_t)pvObj - (uintptr_t)pPage < PAGE_SIZE); /* * Call the constructor? */ if ( pThis->pfnCtor && !ASMAtomicBitTestAndSet(pPage->pbmCtor, iObj)) { int rc = pThis->pfnCtor(hMemCache, pvObj, pThis->pvUser); if (RT_FAILURE(rc)) { ASMAtomicBitClear(pPage->pbmCtor, iObj); RTMemCacheFree(pThis, pvObj); return rc; } } *ppvObj = pvObj; return VINF_SUCCESS; } RTDECL(void *) RTMemCacheAlloc(RTMEMCACHE hMemCache) { void *pvObj; int rc = RTMemCacheAllocEx(hMemCache, &pvObj); if (RT_SUCCESS(rc)) return pvObj; return NULL; } /** * Really frees one object. * * @param pThis The memory cache. * @param pvObj The memory object to free. */ static void rtMemCacheFreeOne(RTMEMCACHEINT *pThis, void *pvObj) { /* Note: Do *NOT* attempt to poison the object! */ /* * Find the cache page. The page structure is at the start of the page. */ PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)(((uintptr_t)pvObj) & ~(uintptr_t)PAGE_OFFSET_MASK); Assert(pPage->pCache == pThis); Assert(ASMAtomicUoReadS32(&pPage->cFree) < (int32_t)pThis->cPerPage); /* * Clear the bitmap bit and update the two object counter. Order matters! */ uintptr_t offObj = (uintptr_t)pvObj - (uintptr_t)pPage->pbObjects; uintptr_t iObj = offObj / pThis->cbObject; Assert(iObj * pThis->cbObject == offObj); Assert(iObj < pThis->cPerPage); AssertReturnVoid(ASMAtomicBitTestAndClear(pPage->pbmAlloc, iObj)); ASMAtomicIncS32(&pPage->cFree); ASMAtomicIncS32(&pThis->cFree); } /** * Really frees a list of 'freed' object. * * @param pThis The memory cache. * @param pHead The head of the list. */ static void rtMemCacheFreeList(RTMEMCACHEINT *pThis, PRTMEMCACHEFREEOBJ pHead) { while (pHead) { PRTMEMCACHEFREEOBJ pFreeMe = pHead; pHead = pHead->pNext; pFreeMe->pNext = NULL; ASMCompilerBarrier(); rtMemCacheFreeOne(pThis, pFreeMe); } } RTDECL(void) RTMemCacheFree(RTMEMCACHE hMemCache, void *pvObj) { if (!pvObj) return; RTMEMCACHEINT *pThis = hMemCache; AssertPtrReturnVoid(pThis); AssertReturnVoid(pThis->u32Magic == RTMEMCACHE_MAGIC); AssertPtr(pvObj); Assert(RT_ALIGN_P(pvObj, pThis->cbAlignment) == pvObj); if (!pThis->fUseFreeList) rtMemCacheFreeOne(pThis, pvObj); else { # ifdef RT_STRICT /* This is the same as the other branch, except it's not actually freed. */ PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)(((uintptr_t)pvObj) & ~(uintptr_t)PAGE_OFFSET_MASK); Assert(pPage->pCache == pThis); Assert(ASMAtomicUoReadS32(&pPage->cFree) < (int32_t)pThis->cPerPage); uintptr_t offObj = (uintptr_t)pvObj - (uintptr_t)pPage->pbObjects; uintptr_t iObj = offObj / pThis->cbObject; Assert(iObj * pThis->cbObject == offObj); Assert(iObj < pThis->cPerPage); AssertReturnVoid(ASMBitTest(pPage->pbmAlloc, (int32_t)iObj)); # endif /* * Push it onto the free stack. */ PRTMEMCACHEFREEOBJ pObj = (PRTMEMCACHEFREEOBJ)pvObj; pObj->pNext = ASMAtomicXchgPtrT(&pThis->pFreeTop, NULL, PRTMEMCACHEFREEOBJ); PRTMEMCACHEFREEOBJ pFreeRace = ASMAtomicXchgPtrT(&pThis->pFreeTop, pObj, PRTMEMCACHEFREEOBJ); if (pFreeRace) rtMemCacheFreeList(pThis, pFreeRace); } }