memcache.cpp revision 64babf0f32eaf36212d54af4a3ce5fe193b24825
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/* $Id$ */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/** @file
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * IPRT - Memory Object Allocation Cache.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Copyright (C) 2006-2010 Sun Microsystems, Inc.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync *
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * available from http://www.virtualbox.org. This file is free software;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * you can redistribute it and/or modify it under the terms of the GNU
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * General Public License (GPL) as published by the Free Software
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync *
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * The contents of this file may alternatively be used under the terms
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * of the Common Development and Distribution License Version 1.0
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * VirtualBox OSE distribution, in which case the provisions of the
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * CDDL are applicable instead of those of the GPL.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync *
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * You may elect to license modified versions of this file under the
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * terms and conditions of either the GPL or the CDDL or both.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync *
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Clara, CA 95054 USA or visit http://www.sun.com if you need
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * additional information or have any questions.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/*******************************************************************************
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync* Header Files *
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync*******************************************************************************/
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include <iprt/memcache.h>
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include "internal/iprt.h"
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include <iprt/assert.h>
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include <iprt/asm.h>
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include <iprt/critsect.h>
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include <iprt/err.h>
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include <iprt/mem.h>
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include <iprt/param.h>
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync#include "internal/magics.h"
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/*******************************************************************************
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync* Structures and Typedefs *
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync*******************************************************************************/
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/** Pointer to a cache instance. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsynctypedef struct RTMEMCACHEINT *PRTMEMCACHEINT;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/** Pointer to a cache page. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsynctypedef struct RTMEMCACHEPAGE *PRTMEMCACHEPAGE;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/**
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * A cache page.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync *
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * This is a page of memory that we split up in to a bunch object sized chunks
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * and hand out to the cache users. The bitmap is updated in an atomic fashion
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * so that we don't have to take any locks when freeing or allocating memory.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsynctypedef struct RTMEMCACHEPAGE
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Pointer to the cache owning this page.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * This is used for validation purposes only. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PRTMEMCACHEINT pCache;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Pointer to the next page.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * This is marked as volatile since we'll be adding new entries to the list
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * without taking any locks. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PRTMEMCACHEPAGE volatile pNext;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** The number of free objects. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int32_t volatile cFree;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** The number of objects on this page. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t cObjects;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Bitmap tracking allocated blocks. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync void volatile *pbmAlloc;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Bitmap tracking which blocks that has been thru the constructor. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync void volatile *pbmCtor;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Pointer to the object array.. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint8_t *pbObjects;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync} RTMEMCACHEPAGE;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/**
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Memory object cache instance.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsynctypedef struct RTMEMCACHEINT
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Magic value (RTMEMCACHE_MAGIC). */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t u32Magic;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** The object size. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t cbObject;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Object alignment. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t cbAlignment;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** The per page object count. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t cPerPage;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Number of bits in the bitmap.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * @remarks This is higher or equal to cPerPage and it is aligned such that
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * the search operation will be most efficient on x86/AMD64. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t cBits;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** The maximum number of objects. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t cMax;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** The total object count. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t volatile cTotal;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** The number of free objects. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int32_t volatile cFree;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Head of the page list. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PRTMEMCACHEPAGE pPageHead;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** This may point to a page with free entries. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PRTMEMCACHEPAGE volatile pPageHint;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Constructor callback. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PFNMEMCACHECTOR pfnCtor;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Destructor callback. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PFNMEMCACHEDTOR pfnDtor;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Callback argument. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync void *pvUser;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /** Critical section serializing page allocation and similar. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTCRITSECT CritSect;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync} RTMEMCACHEINT;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsyncRTDECL(int) RTMemCacheCreate(PRTMEMCACHE phMemCache, size_t cbObject, size_t cbAlignment, uint32_t cMaxObjects,
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PFNMEMCACHECTOR pfnCtor, PFNMEMCACHEDTOR pfnDtor, void *pvUser)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertPtr(phMemCache);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertPtrNull(pfnCtor);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertPtrNull(pfnDtor);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturn(cbObject > 0, VERR_INVALID_PARAMETER);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturn(cbObject <= PAGE_SIZE / 8, VERR_INVALID_PARAMETER);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (cbAlignment == 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync cbAlignment = UINT32_C(1) << ASMBitLastSetU32((uint32_t)cbObject);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (cbAlignment > 64)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync cbAlignment = 64;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync else
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturn(!((cbAlignment - 1) & cbAlignment), VERR_NOT_POWER_OF_TWO);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturn(cbAlignment <= 64, VERR_OUT_OF_RANGE);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Allocate and initialize the instance memory.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTMEMCACHEINT *pThis = (RTMEMCACHEINT *)RTMemAlloc(sizeof(*pThis));
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (!pThis)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return VERR_NO_MEMORY;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int rc = RTCritSectInit(&pThis->CritSect);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (RT_FAILURE(rc))
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTMemFree(pThis);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return rc;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->u32Magic = RTMEMCACHE_MAGIC;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->cbObject = RT_ALIGN_Z(cbObject, cbAlignment);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->cbAlignment = cbAlignment;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->cPerPage = (PAGE_SIZE - RT_ALIGN_Z(sizeof(RTMEMCACHEPAGE), cbAlignment)) / pThis->cbObject;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync while ( RT_ALIGN_Z(sizeof(RTMEMCACHEPAGE), cbAlignment)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync + pThis->cPerPage * pThis->cbObject
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync + RT_ALIGN(pThis->cPerPage, 32) * 2
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync > PAGE_SIZE)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->cPerPage--;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->cBits = RT_ALIGN(pThis->cPerPage, 32);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->cMax = cMaxObjects;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->cTotal = 0;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->cFree = 0;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->pPageHead = NULL;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->pPageHint = NULL;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->pfnCtor = pfnCtor;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->pfnDtor = pfnDtor;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->pvUser = pvUser;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync *phMemCache = pThis;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return VINF_SUCCESS;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync}
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsyncRTDECL(int) RTMemCacheDestroy(RTMEMCACHE hMemCache)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTMEMCACHEINT *pThis = hMemCache;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (!pThis)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return VINF_SUCCESS;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturn(pThis->u32Magic == RTMEMCACHE_MAGIC, VERR_INVALID_HANDLE);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertMsg((uint32_t)pThis->cFree == pThis->cTotal, ("cFree=%u cTotal=%u\n", pThis->cFree, pThis->cTotal));
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Destroy it.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTMEMCACHE_MAGIC_DEAD, RTMEMCACHE_MAGIC), VERR_INVALID_HANDLE);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTCritSectDelete(&pThis->CritSect);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync while (pThis->pPageHead)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PRTMEMCACHEPAGE pPage = pThis->pPageHead;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pThis->pPageHead = pPage->pNext;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pPage->cFree = 0;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (pThis->pfnDtor)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t iObj = pPage->cObjects;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync while (iObj-- > 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (ASMBitTestAndClear(pPage->pbmCtor, iObj))
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync pThis->pfnDtor(hMemCache, pPage->pbObjects + iObj * pThis->cbObject, pThis->pvUser);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTMemPageFree(pPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTMemFree(pThis);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return VINF_SUCCESS;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync}
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/**
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Grows the cache.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync *
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * @returns IPRT status code.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * @param pThis The memory cache instance.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsyncstatic int rtMemCacheGrow(RTMEMCACHEINT *pThis)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Enter the critical section here to avoid allocation races leading to
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * wasted memory (++) and make it easier to link in the new page.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTCritSectEnter(&pThis->CritSect);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int rc = VINF_SUCCESS;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (pThis->cFree < 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Allocate and initialize the new page.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)RTMemPageAlloc(PAGE_SIZE);
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync if (pPage)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync uint32_t const cObjects = RT_MIN(pThis->cPerPage, pThis->cMax - pThis->cTotal);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMMemZeroPage(pPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pPage->pCache = pThis;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pPage->pNext = NULL;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pPage->cFree = cObjects;
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync pPage->cObjects = cObjects;
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync pPage->pbmAlloc = pPage + 1;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pPage->pbmCtor = (uint8_t *)pPage->pbmAlloc + pThis->cBits / 8;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pPage->pbObjects = (uint8_t *)pPage->pbmCtor + pThis->cBits / 8;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pPage->pbObjects = RT_ALIGN_PT(pPage->pbObjects, pThis->cbAlignment, uint8_t *);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /* Mark the bitmap padding and any unused objects as allocated. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync for (uint32_t iBit = cObjects; iBit < pThis->cBits; iBit++)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMBitSet(pPage->pbmAlloc, iBit);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /* Make it the hint. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicWritePtr((void * volatile *)&pThis->pPageHint, pPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /* Link the page. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PRTMEMCACHEPAGE pPrevPage = pThis->pPageHead;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (!pPrevPage)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicWritePtr((void * volatile *)&pThis->pPageHead, pPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync else
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync while (pPrevPage->pNext)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync pPrevPage = pPrevPage->pNext;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicWritePtr((void * volatile *)&pPrevPage->pNext, pPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /* Add it to the page counts. */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicAddS32(&pThis->cFree, cObjects);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicAddU32(&pThis->cTotal, cObjects);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync else
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync rc = VERR_NO_MEMORY;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTCritSectLeave(&pThis->CritSect);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return rc;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync}
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync/**
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Grabs a an object in a page.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * @returns New cFree value on success (0 or higher), -1 on failure.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * @param pPage Pointer to the page.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsyncDECL_FORCE_INLINE(int32_t) rtMemCacheGrabObj(PRTMEMCACHEPAGE pPage)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int32_t cFreeNew = ASMAtomicDecS32(&pPage->cFree);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (cFreeNew < 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicIncS32(&pPage->cFree);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return -1;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return cFreeNew;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync}
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsyncRTDECL(int) RTMemCacheAllocEx(RTMEMCACHE hMemCache, void **ppvObj)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTMEMCACHEINT *pThis = hMemCache;
d273db24f1a69abac22a9c2f9c8251e16b66c47fvboxsync AssertPtrReturn(pThis, VERR_INVALID_PARAMETER);
5a7561300d631625bc381bcc85dd2087f34d0bf9vboxsync AssertReturn(pThis->u32Magic == RTMEMCACHE_MAGIC, VERR_INVALID_PARAMETER);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Try grab a free object at the cache level.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int32_t cNewFree = ASMAtomicDecS32(&pThis->cFree);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (cNewFree < 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync uint32_t cTotal = ASMAtomicUoReadU32(&pThis->cTotal);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if ( (uint32_t)(cTotal + -cNewFree) > pThis->cMax
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync || (uint32_t)(cTotal + -cNewFree) <= cTotal)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicIncS32(&pThis->cFree);
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync return VERR_MEM_CACHE_MAX_SIZE;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int rc = rtMemCacheGrow(pThis);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (RT_FAILURE(rc))
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicIncS32(&pThis->cFree);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return rc;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Grab a free object at the page level.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)ASMAtomicReadPtr((void * volatile *)&pThis->pPageHint);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int32_t iObj = pPage ? rtMemCacheGrabObj(pPage) : -1;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (iObj < 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync for (unsigned cLoops = 0; ; cLoops++)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync for (pPage = pThis->pPageHead; pPage; pPage = pPage->pNext)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync iObj = rtMemCacheGrabObj(pPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (iObj >= 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (iObj > 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicWritePtr((void * volatile *)&pThis->pPageHint, pPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync break;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (iObj >= 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync break;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync Assert(cLoops != 2);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync Assert(cLoops < 10);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync Assert(iObj >= 0);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync Assert((uint32_t)iObj < pThis->cMax);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Find a free object in the allocation bitmap. Use the new cFree count
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * as a hint.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (ASMAtomicBitTestAndSet(pPage->pbmAlloc, iObj))
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync for (unsigned cLoops2 = 0;; cLoops2++)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync iObj = ASMBitFirstClear(pPage->pbmAlloc, pThis->cBits);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (iObj < 0)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMMemoryFence();
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync else if (!ASMAtomicBitTestAndSet(pPage->pbmAlloc, iObj))
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync break;
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync Assert(cLoops2 != 40);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync Assert(iObj >= 0);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync void *pvObj = &pPage->pbObjects[iObj * pThis->cbObject];
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync Assert((uintptr_t)pvObj - (uintptr_t)pPage < PAGE_SIZE);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Call the constructor?
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if ( pThis->pfnCtor
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync && !ASMAtomicBitTestAndSet(pPage->pbmCtor, iObj))
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int rc = pThis->pfnCtor(hMemCache, pvObj, pThis->pvUser);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (RT_FAILURE(rc))
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync {
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicBitClear(pPage->pbmCtor, iObj);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTMemCacheFree(pThis, pvObj);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return rc;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync }
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync *ppvObj = pvObj;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return VINF_SUCCESS;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync}
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsyncRTDECL(void *) RTMemCacheAlloc(RTMEMCACHE hMemCache)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync void *pvObj;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync int rc = RTMemCacheAllocEx(hMemCache, &pvObj);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (RT_SUCCESS(rc))
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return pvObj;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return NULL;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync}
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsyncRTDECL(void) RTMemCacheFree(RTMEMCACHE hMemCache, void *pvObj)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync{
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync if (!pvObj)
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync return;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync RTMEMCACHEINT *pThis = hMemCache;
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertPtrReturnVoid(pThis);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturnVoid(pThis->u32Magic == RTMEMCACHE_MAGIC);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertPtr(pvObj);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync Assert(RT_ALIGN_P(pvObj, pThis->cbAlignment) == pvObj);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /* Note: Do *NOT* attempt to poison the object if we have a constructor
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync or/and destructor! */
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Find the cache page. The page structure is at the start of the page.
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)(((uintptr_t)pvObj) & ~(uintptr_t)PAGE_OFFSET_MASK);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturnVoid(pPage->pCache == pThis);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturnVoid(ASMAtomicUoReadS32(&pPage->cFree) < (int32_t)pThis->cPerPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync /*
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync * Clear the bitmap bit and update the two object counter. Order matters!
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync */
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync uintptr_t offObj = (uintptr_t)pvObj - (uintptr_t)pPage->pbObjects;
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync uintptr_t iObj = offObj / pThis->cbObject;
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync AssertReturnVoid(iObj * pThis->cbObject == offObj);
64babf0f32eaf36212d54af4a3ce5fe193b24825vboxsync Assert(iObj < pThis->cPerPage);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync AssertReturnVoid(ASMAtomicBitTestAndClear(pPage->pbmAlloc, iObj));
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicIncS32(&pPage->cFree);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync ASMAtomicIncS32(&pThis->cFree);
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync}
66b15150e35f27f9499bb0a8399e452d6a04895dvboxsync