memcache.cpp@ 26452

Last change on this file since 26452 was 26452, checked in by vboxsync, 15 years ago
iprt/memcache.h: Some more optimizations and more benchmarks.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 18.1 KB

Line
1	/* $Id: memcache.cpp 26452 2010-02-11 18:41:06Z vboxsync $ */
2	/** @file
3	* IPRT - Memory Object Allocation Cache.
4	*/
5
6	/*
7	* Copyright (C) 2006-2010 Sun Microsystems, Inc.
8	*
9	* This file is part of VirtualBox Open Source Edition (OSE), as
10	* available from http://www.virtualbox.org. This file is free software;
11	* you can redistribute it and/or modify it under the terms of the GNU
12	* General Public License (GPL) as published by the Free Software
13	* Foundation, in version 2 as it comes in the "COPYING" file of the
14	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16	*
17	* The contents of this file may alternatively be used under the terms
18	* of the Common Development and Distribution License Version 1.0
19	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20	* VirtualBox OSE distribution, in which case the provisions of the
21	* CDDL are applicable instead of those of the GPL.
22	*
23	* You may elect to license modified versions of this file under the
24	* terms and conditions of either the GPL or the CDDL or both.
25	*
26	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
27	* Clara, CA 95054 USA or visit http://www.sun.com if you need
28	* additional information or have any questions.
29	*/
30
31
32	/*******************************************************************************
33	* Header Files *
34	*******************************************************************************/
35	#include <iprt/memcache.h>
36	#include "internal/iprt.h"
37
38	#include <iprt/assert.h>
39	#include <iprt/asm.h>
40	#include <iprt/critsect.h>
41	#include <iprt/err.h>
42	#include <iprt/mem.h>
43	#include <iprt/param.h>
44
45	#include "internal/magics.h"
46
47
48	/*******************************************************************************
49	* Structures and Typedefs *
50	*******************************************************************************/
51	/** Pointer to a cache instance. */
52	typedef struct RTMEMCACHEINT *PRTMEMCACHEINT;
53	/** Pointer to a cache page. */
54	typedef struct RTMEMCACHEPAGE *PRTMEMCACHEPAGE;
55
56
57
58	/**
59	* A free object.
60	*
61	* @remarks This only works if the objects don't have a constructor or
62	* destructor and are big enough.
63	*/
64	typedef struct RTMEMCACHEFREEOBJ
65	{
66	/** Pointer to the next free object */
67	struct RTMEMCACHEFREEOBJ * volatile pNext;
68	} RTMEMCACHEFREEOBJ;
69	/** Pointer to a free object. */
70	typedef RTMEMCACHEFREEOBJ *PRTMEMCACHEFREEOBJ;
71
72
73	/**
74	* A cache page.
75	*
76	* This is a page of memory that we split up in to a bunch object sized chunks
77	* and hand out to the cache users. The bitmap is updated in an atomic fashion
78	* so that we don't have to take any locks when freeing or allocating memory.
79	*/
80	typedef struct RTMEMCACHEPAGE
81	{
82	/** Pointer to the cache owning this page.
83	* This is used for validation purposes only. */
84	PRTMEMCACHEINT pCache;
85	/** Pointer to the next page.
86	* This is marked as volatile since we'll be adding new entries to the list
87	* without taking any locks. */
88	PRTMEMCACHEPAGE volatile pNext;
89	/** Bitmap tracking allocated blocks. */
90	void volatile *pbmAlloc;
91	/** Bitmap tracking which blocks that has been thru the constructor. */
92	void volatile *pbmCtor;
93	/** Pointer to the object array.. */
94	uint8_t *pbObjects;
95	/** The number of objects on this page. */
96	uint32_t cObjects;
97
98	/** Padding to force cFree into the next cache line. (ASSUMES CL = 64) */
99	uint8_t abPadding[ARCH_BITS == 32 ? 64 - 64 : 64 - 58 - 4];
100	/** The number of free objects. */
101	int32_t volatile cFree;
102	} RTMEMCACHEPAGE;
103	AssertCompileMemberOffset(RTMEMCACHEPAGE, cFree, 64);
104
105
106	/**
107	* Memory object cache instance.
108	*/
109	typedef struct RTMEMCACHEINT
110	{
111	/** Magic value (RTMEMCACHE_MAGIC). */
112	uint32_t u32Magic;
113	/** The object size. */
114	uint32_t cbObject;
115	/** Object alignment. */
116	uint32_t cbAlignment;
117	/** The per page object count. */
118	uint32_t cPerPage;
119	/** Number of bits in the bitmap.
120	* @remarks This is higher or equal to cPerPage and it is aligned such that
121	* the search operation will be most efficient on x86/AMD64. */
122	uint32_t cBits;
123	/** The maximum number of objects. */
124	uint32_t cMax;
125	/** Whether to the use the free list or not. */
126	bool fUseFreeList;
127	/** Head of the page list. */
128	PRTMEMCACHEPAGE pPageHead;
129	/** Constructor callback. */
130	PFNMEMCACHECTOR pfnCtor;
131	/** Destructor callback. */
132	PFNMEMCACHEDTOR pfnDtor;
133	/** Callback argument. */
134	void *pvUser;
135	/** Critical section serializing page allocation and similar. */
136	RTCRITSECT CritSect;
137
138	/** The total object count. */
139	uint32_t volatile cTotal;
140	/** The number of free objects. */
141	int32_t volatile cFree;
142	/** This may point to a page with free entries. */
143	PRTMEMCACHEPAGE volatile pPageHint;
144	/** Stack of free items.
145	* These are marked as used in the allocation bitmaps.
146	*
147	* @todo This doesn't scale well when several threads are beating on the
148	* cache. Also, it totally doesn't work when we've got a
149	* constructor/destructor around or the objects are too small. */
150	PRTMEMCACHEFREEOBJ volatile pFreeTop;
151	} RTMEMCACHEINT;
152
153
154
155	RTDECL(int) RTMemCacheCreate(PRTMEMCACHE phMemCache, size_t cbObject, size_t cbAlignment, uint32_t cMaxObjects,
156	PFNMEMCACHECTOR pfnCtor, PFNMEMCACHEDTOR pfnDtor, void *pvUser, uint32_t fFlags)
157
158	{
159	AssertPtr(phMemCache);
160	AssertPtrNull(pfnCtor);
161	AssertPtrNull(pfnDtor);
162	AssertReturn(!pfnDtor \|\| pfnCtor, VERR_INVALID_PARAMETER);
163	AssertReturn(cbObject > 0, VERR_INVALID_PARAMETER);
164	AssertReturn(cbObject <= PAGE_SIZE / 8, VERR_INVALID_PARAMETER);
165	AssertReturn(!fFlags, VERR_INVALID_PARAMETER);
166
167	if (cbAlignment == 0)
168	{
169	cbAlignment = UINT32_C(1) << ASMBitLastSetU32((uint32_t)cbObject);
170	if (cbAlignment > 64)
171	cbAlignment = 64;
172	}
173	else
174	{
175	AssertReturn(!((cbAlignment - 1) & cbAlignment), VERR_NOT_POWER_OF_TWO);
176	AssertReturn(cbAlignment <= 64, VERR_OUT_OF_RANGE);
177	}
178
179	/*
180	* Allocate and initialize the instance memory.
181	*/
182	RTMEMCACHEINT pThis = (RTMEMCACHEINT )RTMemAlloc(sizeof(*pThis));
183	if (!pThis)
184	return VERR_NO_MEMORY;
185	int rc = RTCritSectInit(&pThis->CritSect);
186	if (RT_FAILURE(rc))
187	{
188	RTMemFree(pThis);
189	return rc;
190	}
191
192	pThis->u32Magic = RTMEMCACHE_MAGIC;
193	pThis->cbObject = RT_ALIGN_Z(cbObject, cbAlignment);
194	pThis->cbAlignment = cbAlignment;
195	pThis->cPerPage = (PAGE_SIZE - RT_ALIGN_Z(sizeof(RTMEMCACHEPAGE), cbAlignment)) / pThis->cbObject;
196	while ( RT_ALIGN_Z(sizeof(RTMEMCACHEPAGE), RT_MIN(cbAlignment, 8))
197	+ pThis->cPerPage * pThis->cbObject
198	+ RT_ALIGN(pThis->cPerPage, 64) / 8 * 2
199	> PAGE_SIZE)
200	pThis->cPerPage--;
201	pThis->cBits = RT_ALIGN(pThis->cPerPage, 64);
202	pThis->cMax = cMaxObjects;
203	pThis->fUseFreeList = cbObject >= sizeof(RTMEMCACHEFREEOBJ)
204	&& !pfnCtor
205	&& !pfnDtor;
206	pThis->pPageHead = NULL;
207	pThis->pfnCtor = pfnCtor;
208	pThis->pfnDtor = pfnDtor;
209	pThis->pvUser = pvUser;
210	pThis->cTotal = 0;
211	pThis->cFree = 0;
212	pThis->pPageHint = NULL;
213	pThis->pFreeTop = NULL;
214
215	*phMemCache = pThis;
216	return VINF_SUCCESS;
217	}
218
219
220	RTDECL(int) RTMemCacheDestroy(RTMEMCACHE hMemCache)
221	{
222	RTMEMCACHEINT *pThis = hMemCache;
223	if (!pThis)
224	return VINF_SUCCESS;
225	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
226	AssertReturn(pThis->u32Magic == RTMEMCACHE_MAGIC, VERR_INVALID_HANDLE);
227	#ifdef RT_STRICT
228	uint32_t cFree = pThis->cFree;
229	for (PRTMEMCACHEFREEOBJ pFree = pThis->pFreeTop; pFree; pFree = pFree->pNext)
230	cFree++;
231	AssertMsg(cFree == pThis->cTotal, ("cFree=%u cTotal=%u\n", cFree, pThis->cTotal));
232	#endif
233
234	/*
235	* Destroy it.
236	*/
237	AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTMEMCACHE_MAGIC_DEAD, RTMEMCACHE_MAGIC), VERR_INVALID_HANDLE);
238	RTCritSectDelete(&pThis->CritSect);
239
240	while (pThis->pPageHead)
241	{
242	PRTMEMCACHEPAGE pPage = pThis->pPageHead;
243	pThis->pPageHead = pPage->pNext;
244	pPage->cFree = 0;
245
246	if (pThis->pfnDtor)
247	{
248	uint32_t iObj = pPage->cObjects;
249	while (iObj-- > 0)
250	if (ASMBitTestAndClear(pPage->pbmCtor, iObj))
251	pThis->pfnDtor(hMemCache, pPage->pbObjects + iObj * pThis->cbObject, pThis->pvUser);
252	}
253
254	RTMemPageFree(pPage);
255	}
256
257	RTMemFree(pThis);
258	return VINF_SUCCESS;
259	}
260
261
262	/**
263	* Grows the cache.
264	*
265	* @returns IPRT status code.
266	* @param pThis The memory cache instance.
267	*/
268	static int rtMemCacheGrow(RTMEMCACHEINT *pThis)
269	{
270	/*
271	* Enter the critical section here to avoid allocation races leading to
272	* wasted memory (++) and make it easier to link in the new page.
273	*/
274	RTCritSectEnter(&pThis->CritSect);
275	int rc = VINF_SUCCESS;
276	if (pThis->cFree < 0)
277	{
278	/*
279	* Allocate and initialize the new page.
280	*
281	* We put the constructor bitmap at the lower end right after cFree.
282	* We then push the object array to the end of the page and place the
283	* allocation bitmap below it. The hope is to increase the chance that
284	* the allocation bitmap is in a different cache line than cFree since
285	* this increases performance markably when lots of threads are beating
286	* on the cache.
287	*/
288	PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)RTMemPageAlloc(PAGE_SIZE);
289	if (pPage)
290	{
291	uint32_t const cObjects = RT_MIN(pThis->cPerPage, pThis->cMax - pThis->cTotal);
292
293	ASMMemZeroPage(pPage);
294	pPage->pCache = pThis;
295	pPage->pNext = NULL;
296	pPage->cFree = cObjects;
297	pPage->cObjects = cObjects;
298	uint8_t pb = (uint8_t )(pPage + 1);
299	pb = RT_ALIGN_PT(pb, 8, uint8_t *);
300	pPage->pbmCtor = pb;
301	pb += pThis->cBits / 8 * 2;
302	pb = (uint8_t )pPage + PAGE_SIZE - pThis->cbObject cObjects;
303	pPage->pbObjects = pb; Assert(RT_ALIGN_P(pb, pThis->cbAlignment) == pb);
304	pb -= pThis->cBits / 8;
305	pb = (uint8_t *)((uintptr_t)pb & ~(uintptr_t)7);
306	pPage->pbmAlloc = pb;
307	Assert((uintptr_t)pPage->pbmCtor + pThis->cBits / 8 <= (uintptr_t)pPage->pbmAlloc);
308
309	/* Mark the bitmap padding and any unused objects as allocated. */
310	for (uint32_t iBit = cObjects; iBit < pThis->cBits; iBit++)
311	ASMBitSet(pPage->pbmAlloc, iBit);
312
313	/* Make it the hint. */
314	ASMAtomicWritePtr((void * volatile *)&pThis->pPageHint, pPage);
315
316	/* Link the page. */
317	PRTMEMCACHEPAGE pPrevPage = pThis->pPageHead;
318	if (!pPrevPage)
319	ASMAtomicWritePtr((void * volatile *)&pThis->pPageHead, pPage);
320	else
321	{
322	while (pPrevPage->pNext)
323	pPrevPage = pPrevPage->pNext;
324	ASMAtomicWritePtr((void * volatile *)&pPrevPage->pNext, pPage);
325	}
326
327	/* Add it to the page counts. */
328	ASMAtomicAddS32(&pThis->cFree, cObjects);
329	ASMAtomicAddU32(&pThis->cTotal, cObjects);
330	}
331	else
332	rc = VERR_NO_MEMORY;
333	}
334	RTCritSectLeave(&pThis->CritSect);
335	return rc;
336	}
337
338
339	/**
340	* Grabs a an object in a page.
341	* @returns New cFree value on success (0 or higher), -1 on failure.
342	* @param pPage Pointer to the page.
343	*/
344	DECL_FORCE_INLINE(int32_t) rtMemCacheGrabObj(PRTMEMCACHEPAGE pPage)
345	{
346	int32_t cFreeNew = ASMAtomicDecS32(&pPage->cFree);
347	if (cFreeNew < 0)
348	{
349	ASMAtomicIncS32(&pPage->cFree);
350	return -1;
351	}
352	return cFreeNew;
353	}
354
355
356	RTDECL(int) RTMemCacheAllocEx(RTMEMCACHE hMemCache, void **ppvObj)
357	{
358	RTMEMCACHEINT *pThis = hMemCache;
359	AssertPtrReturn(pThis, VERR_INVALID_PARAMETER);
360	AssertReturn(pThis->u32Magic == RTMEMCACHE_MAGIC, VERR_INVALID_PARAMETER);
361
362	/*
363	* Try grab a free object from the stack.
364	*/
365	PRTMEMCACHEFREEOBJ pObj = (PRTMEMCACHEFREEOBJ)ASMAtomicUoReadPtr((void * volatile *)&pThis->pFreeTop);
366	if (pObj)
367	{
368	PRTMEMCACHEFREEOBJ pNext;
369	do
370	{
371	pNext = (PRTMEMCACHEFREEOBJ)ASMAtomicUoReadPtr((void * volatile *)&pObj->pNext);
372	if (ASMAtomicCmpXchgPtr((void * volatile *)&pThis->pFreeTop, pNext, pObj))
373	{
374	*ppvObj = pObj;
375	return VINF_SUCCESS;
376	}
377	pObj = (PRTMEMCACHEFREEOBJ)ASMAtomicUoReadPtr((void * volatile *)&pThis->pFreeTop);
378	} while (pObj);
379	}
380
381	/*
382	* Try grab a free object at the cache level.
383	*/
384	int32_t cNewFree = ASMAtomicDecS32(&pThis->cFree);
385	if (RT_LIKELY(cNewFree < 0))
386	{
387	uint32_t cTotal = ASMAtomicUoReadU32(&pThis->cTotal);
388	if ( (uint32_t)(cTotal + -cNewFree) > pThis->cMax
389	\|\| (uint32_t)(cTotal + -cNewFree) <= cTotal)
390	{
391	ASMAtomicIncS32(&pThis->cFree);
392	return VERR_MEM_CACHE_MAX_SIZE;
393	}
394
395	int rc = rtMemCacheGrow(pThis);
396	if (RT_FAILURE(rc))
397	{
398	ASMAtomicIncS32(&pThis->cFree);
399	return rc;
400	}
401	}
402
403	/*
404	* Grab a free object at the page level.
405	*/
406	PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)ASMAtomicReadPtr((void * volatile *)&pThis->pPageHint);
407	int32_t iObj = pPage ? rtMemCacheGrabObj(pPage) : -1;
408	if (iObj < 0)
409	{
410	for (unsigned cLoops = 0; ; cLoops++)
411	{
412	for (pPage = pThis->pPageHead; pPage; pPage = pPage->pNext)
413	{
414	iObj = rtMemCacheGrabObj(pPage);
415	if (iObj >= 0)
416	{
417	if (iObj > 0)
418	ASMAtomicWritePtr((void * volatile *)&pThis->pPageHint, pPage);
419	break;
420	}
421	}
422	if (iObj >= 0)
423	break;
424	Assert(cLoops != 2);
425	Assert(cLoops < 10);
426	}
427	}
428	Assert(iObj >= 0);
429	Assert((uint32_t)iObj < pThis->cMax);
430
431	/*
432	* Find a free object in the allocation bitmap. Use the new cFree count
433	* as a hint.
434	*/
435	if (ASMAtomicBitTestAndSet(pPage->pbmAlloc, iObj))
436	{
437	for (unsigned cLoops2 = 0;; cLoops2++)
438	{
439	iObj = ASMBitFirstClear(pPage->pbmAlloc, pThis->cBits);
440	if (RT_LIKELY(iObj >= 0))
441	{
442	if (!ASMAtomicBitTestAndSet(pPage->pbmAlloc, iObj))
443	break;
444	}
445	else
446	ASMMemoryFence();
447	Assert(cLoops2 != 40);
448	}
449	Assert(iObj >= 0);
450	}
451	void pvObj = &pPage->pbObjects[iObj pThis->cbObject];
452	Assert((uintptr_t)pvObj - (uintptr_t)pPage < PAGE_SIZE);
453
454	/*
455	* Call the constructor?
456	*/
457	if ( pThis->pfnCtor
458	&& !ASMAtomicBitTestAndSet(pPage->pbmCtor, iObj))
459	{
460	int rc = pThis->pfnCtor(hMemCache, pvObj, pThis->pvUser);
461	if (RT_FAILURE(rc))
462	{
463	ASMAtomicBitClear(pPage->pbmCtor, iObj);
464	RTMemCacheFree(pThis, pvObj);
465	return rc;
466	}
467	}
468
469	*ppvObj = pvObj;
470	return VINF_SUCCESS;
471	}
472
473
474	RTDECL(void *) RTMemCacheAlloc(RTMEMCACHE hMemCache)
475	{
476	void *pvObj;
477	int rc = RTMemCacheAllocEx(hMemCache, &pvObj);
478	if (RT_SUCCESS(rc))
479	return pvObj;
480	return NULL;
481	}
482
483
484	RTDECL(void) RTMemCacheFree(RTMEMCACHE hMemCache, void *pvObj)
485	{
486	if (!pvObj)
487	return;
488
489	RTMEMCACHEINT *pThis = hMemCache;
490	AssertPtrReturnVoid(pThis);
491	AssertReturnVoid(pThis->u32Magic == RTMEMCACHE_MAGIC);
492
493	AssertPtr(pvObj);
494	Assert(RT_ALIGN_P(pvObj, pThis->cbAlignment) == pvObj);
495
496	if (pThis->fUseFreeList)
497	{
498	# ifdef RT_STRICT
499	/* This is the same as the other branch, except it's not actually freed. */
500	PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)(((uintptr_t)pvObj) & ~(uintptr_t)PAGE_OFFSET_MASK);
501	Assert(pPage->pCache == pThis);
502	Assert(ASMAtomicUoReadS32(&pPage->cFree) < (int32_t)pThis->cPerPage);
503	uintptr_t offObj = (uintptr_t)pvObj - (uintptr_t)pPage->pbObjects;
504	uintptr_t iObj = offObj / pThis->cbObject;
505	Assert(iObj * pThis->cbObject == offObj);
506	Assert(iObj < pThis->cPerPage);
507	AssertReturnVoid(ASMBitTest(pPage->pbmAlloc, iObj));
508	# endif
509
510	/*
511	* Push it onto the free stack.
512	*/
513	PRTMEMCACHEFREEOBJ pObj = (PRTMEMCACHEFREEOBJ)pvObj;
514	PRTMEMCACHEFREEOBJ pNext;
515	do
516	{
517	pNext = (PRTMEMCACHEFREEOBJ)ASMAtomicUoReadPtr((void * volatile *)&pThis->pFreeTop);
518	pObj->pNext = pNext;
519	} while (!ASMAtomicCmpXchgPtr((void * volatile *)&pThis->pFreeTop, pObj, pNext));
520	}
521	else
522	{
523	/* Note: Do NOT attempt to poison the object if we have a constructor
524	or/and destructor! */
525
526	/*
527	* Find the cache page. The page structure is at the start of the page.
528	*/
529	PRTMEMCACHEPAGE pPage = (PRTMEMCACHEPAGE)(((uintptr_t)pvObj) & ~(uintptr_t)PAGE_OFFSET_MASK);
530	Assert(pPage->pCache == pThis);
531	Assert(ASMAtomicUoReadS32(&pPage->cFree) < (int32_t)pThis->cPerPage);
532
533	/*
534	* Clear the bitmap bit and update the two object counter. Order matters!
535	*/
536	uintptr_t offObj = (uintptr_t)pvObj - (uintptr_t)pPage->pbObjects;
537	uintptr_t iObj = offObj / pThis->cbObject;
538	Assert(iObj * pThis->cbObject == offObj);
539	Assert(iObj < pThis->cPerPage);
540	AssertReturnVoid(ASMAtomicBitTestAndClear(pPage->pbmAlloc, iObj));
541
542	ASMAtomicIncS32(&pPage->cFree);
543	ASMAtomicIncS32(&pThis->cFree);
544	}
545	}
546

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/Runtime/common/alloc/memcache.cpp@ 26452

Download in other formats: