memcache.cpp@ 32568

Last change on this file since 32568 was 30111, checked in by vboxsync, 15 years ago
iprt/asm.h,: Revised the ASMAtomicPtr functions and macros. The new saves lots of unsafe (void * volatile *) casts as well as adding some type safety when using GCC (typeof rulez).
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 17.7 KB

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

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

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

Download in other formats: